摘要：二叉查找樹是一種查找效率非常高的數(shù)據(jù)結(jié)構(gòu)，它有三個特點(diǎn)。二叉查找樹的結(jié)構(gòu)不適合數(shù)據(jù)庫，因?yàn)樗牟檎倚逝c層數(shù)相關(guān)。樹是對二叉查找樹的改進(jìn)。備份機(jī)制保存數(shù)據(jù)庫的副本。

轉(zhuǎn)載自:阮一峰的網(wǎng)絡(luò)日志

  
所有應(yīng)用軟件之中，數(shù)據(jù)庫可能是最復(fù)雜的。

  MySQL的手冊有3000多頁，PostgreSQL的手冊有2000多頁，Oracle的手冊更是比它們相加還要厚。

  但是，自己寫一個最簡單的數(shù)據(jù)庫，做起來并不難。Reddit上面有一個帖子，只用了幾百個字，就把原理講清楚了。下面是我根據(jù)這個帖子整理的內(nèi)容。

數(shù)據(jù)以文本形式保存

    
第一步，就是將所要保存的數(shù)據(jù)，寫入文本文件。這個文本文件就是你的數(shù)據(jù)庫。

    為了方便讀取，數(shù)據(jù)必須分成記錄，每一條記錄的長度規(guī)定為等長。比如，假定每條記錄的長度是800字節(jié)，那么第5條記錄的開始位置就在3200字節(jié)。

    大多數(shù)時候，我們不知道某一條記錄在第幾個位置，只知道主鍵（primary key）的值。這時為了讀取數(shù)據(jù)，可以一條條比對記錄。但是這樣做效率太低，實(shí)際應(yīng)用中，數(shù)據(jù)庫往往采用B樹（B-tree）格式儲存數(shù)據(jù)。
  

  
要理解B樹，必須從二叉查找樹（Binary search tree）講起。


  二叉查找樹是一種查找效率非常高的數(shù)據(jù)結(jié)構(gòu)，它有三個特點(diǎn)。

1. 每個節(jié)點(diǎn)最多只有兩個子樹。
2. 左子樹都為小于父節(jié)點(diǎn)的值，右子樹都為大于父節(jié)點(diǎn)的值。
3. 在n個節(jié)點(diǎn)中找到目標(biāo)值，一般只需要log(n)次比較。

  
二叉查找樹的結(jié)構(gòu)不適合數(shù)據(jù)庫，因?yàn)樗牟檎倚逝c層數(shù)相關(guān)。越處在下層的數(shù)據(jù)，就需要越多次比較。極端情況下，n個數(shù)據(jù)需要n次比較才能找到目標(biāo)值。對于數(shù)據(jù)庫來說，每進(jìn)入一層，就要從硬盤讀取一次數(shù)據(jù)，這非常致命，因?yàn)橛脖P的讀取時間遠(yuǎn)遠(yuǎn)大于數(shù)據(jù)處理時間，數(shù)據(jù)庫讀取硬盤的次數(shù)越少越好。

  B樹是對二叉查找樹的改進(jìn)。它的設(shè)計思想是，將相關(guān)數(shù)據(jù)盡量集中在一起，以便一次讀取多個數(shù)據(jù)，減少硬盤操作次數(shù)。


  B樹的特點(diǎn)也有三個。

1. 一個節(jié)點(diǎn)可以容納多個值。比如上圖中，最多的一個節(jié)點(diǎn)容納了4個值。
2. 除非數(shù)據(jù)已經(jīng)填滿，否則不會增加新的層。也就是說，B樹追求"層"越少越好。
3. 子節(jié)點(diǎn)中的值，與父節(jié)點(diǎn)中的值，有嚴(yán)格的大小對應(yīng)關(guān)系。一般來說，如果父節(jié)點(diǎn)有a個值，那么就有a+1個子節(jié)點(diǎn)。比如上圖中，父節(jié)點(diǎn)有兩個值（7和16），就對應(yīng)三個子節(jié)點(diǎn)，第一個子節(jié)點(diǎn)都是小于7的值，最后一個子節(jié)點(diǎn)都是大于16的值，中間的子節(jié)點(diǎn)就是7和16之間的值。

  
這種數(shù)據(jù)結(jié)構(gòu)，非常有利于減少讀取硬盤的次數(shù)。假定一個節(jié)點(diǎn)可以容納100(a)個值，那么3(n)層的B樹最大可以容納1030300((a+1)^(n-1)*a)個數(shù)據(jù)，如果換成二叉查找樹，則需要20層！假定操作系統(tǒng)一次讀取一個節(jié)點(diǎn)，并且根節(jié)點(diǎn)保留在內(nèi)存中，那么B樹在100萬個數(shù)據(jù)中查找目標(biāo)值，只需要讀取兩次硬盤。

索引

    
數(shù)據(jù)庫以B樹格式儲存，只解決了按照"主鍵"查找數(shù)據(jù)的問題。如果想查找其他字段，就需要建立索引（index）。

    所謂索引，就是以某個字段為關(guān)鍵字的B樹文件。假定有一張"雇員表"，包含了員工號（主鍵）和姓名兩個字段。可以對姓名建立索引文件，該文件以B樹格式對姓名進(jìn)行儲存，每個姓名后面是其在數(shù)據(jù)庫中的位置（即第幾條記錄）。查找姓名的時候，先從索引中找到對應(yīng)第幾條記錄，然后再從表格中讀取。

    這種索引查找方法，叫做"索引順序存取方法"（Indexed Sequential Access Method），縮寫為ISAM。它已經(jīng)有多種實(shí)現(xiàn)（比如C-ISAM庫和D-ISAM庫），只要使用這些代碼庫，就能自己寫一個最簡單的數(shù)據(jù)庫。
  

  
部署了最基本的數(shù)據(jù)存?。òㄋ饕┮院螅€可以實(shí)現(xiàn)一些高級功能。

  （1）SQL語言是數(shù)據(jù)庫通用操作語言，所以需要一個SQL解析器，將SQL命令解析為對應(yīng)的ISAM操作。

  （2）數(shù)據(jù)庫連接（join）是指數(shù)據(jù)庫的兩張表通過"外鍵"，建立連接關(guān)系。你需要對這種操作進(jìn)行優(yōu)化。

  （3）數(shù)據(jù)庫交易（transaction）是指批量進(jìn)行一系列數(shù)據(jù)庫操作，只要有一步不成功，整個操作都不成功。所以需要有一個"操作日志"，以便失敗時對操作進(jìn)行回滾。

  （4）備份機(jī)制：保存數(shù)據(jù)庫的副本。

  （5）遠(yuǎn)程操作：使得用戶可以在不同的機(jī)器上，通過TCP/IP協(xié)議操作數(shù)據(jù)庫。

  （完）