B+樹在數(shù)據(jù)庫(kù)中的應(yīng)用

{

為什么使用B+樹?言簡(jiǎn)意賅，就是因?yàn)椋?/P>

1.文件很大，不可能全部存儲(chǔ)在內(nèi)存中，故要存儲(chǔ)到磁盤上

2.索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)(為什么使用B-/+Tree，還跟磁盤存取原理有關(guān)。)

3.局部性原理與磁盤預(yù)讀，預(yù)讀的長(zhǎng)度一般為頁(yè)(page)的整倍數(shù)，(在許多操作系統(tǒng)中，頁(yè)得大小通常為4k)

4.數(shù)據(jù)庫(kù)系統(tǒng)巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入，(由于節(jié)點(diǎn)中有兩個(gè)數(shù)組，所以地址連續(xù))。而紅黑樹這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)(父子)物理上可能很遠(yuǎn)，無法利用局部性

InnoDB 與 MyISAM 結(jié)構(gòu)上的區(qū)別

1.InnoDB的主鍵索引 ，MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引，所以必須有主鍵，如果沒有顯示定義，自動(dòng)為生成一個(gè)隱含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類型為長(zhǎng)整形2.InnoDB的輔助索引(Secondary Index， 也就是非主鍵索引)也會(huì)包含主鍵列，比如名字建立索引，內(nèi)部節(jié)點(diǎn) 會(huì)包含名字，葉子節(jié)點(diǎn)會(huì)包含該名字對(duì)應(yīng)的主鍵的值，如果主鍵定義的比較大，其他索引也將很大3.MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，索引文件葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址，指向數(shù)據(jù)文件中對(duì)應(yīng)的值，每個(gè)節(jié)點(diǎn)只有該索引列的值

4.MyISAM主索引和輔助索引(Secondary key)在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求key是唯一的，輔助索引可以重復(fù)，

(由于MyISAM輔助索引在葉子節(jié)點(diǎn)上存儲(chǔ)的是數(shù)據(jù)記錄的地址，和主鍵索引一樣，所以相對(duì)于B+的InnoDB可通過輔助索引

快速找到所有的數(shù)據(jù)，而不需要再遍歷一邊主鍵索引，所以適用于OLAP)

InnoDB索引和MyISAM索引的區(qū)別：

一是主索引的區(qū)別，InnoDB的數(shù)據(jù)文件本身就是索引文件。而MyISAM的索引和數(shù)據(jù)是分開的。

二是輔助索引的區(qū)別：InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒有多大區(qū)別。

}

1. 索引在數(shù)據(jù)庫(kù)中的作用

在數(shù)據(jù)庫(kù)系統(tǒng)的使用過程當(dāng)中，數(shù)據(jù)的查詢是使用最頻繁的一種數(shù)據(jù)操作。

最基本的查詢算法當(dāng)然是順序查找(linear search)，遍歷表然后逐行匹配行值是否等于待查找的關(guān)鍵字，其時(shí)間復(fù)雜度為O(n)。但時(shí)間復(fù)雜度為O(n)的算法規(guī)模小的表，負(fù)載輕的數(shù)據(jù)庫(kù)，也能有好的性能。 但是數(shù)據(jù)增大的時(shí)候，時(shí)間復(fù)雜度為O(n)的算法顯然是糟糕的，性能就很快下降了。

好在計(jì)算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法，例如二分查找(binary search)、二叉樹查找(binary tree search)等。如果稍微分析一下會(huì)發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹查找只能應(yīng)用于二叉查找樹上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)(例如，理論上不可能同時(shí)將兩列都按順序進(jìn)行組織)，所以，在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向)數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

索引是對(duì)數(shù)據(jù)庫(kù)表 中一個(gè)或多個(gè)列的值進(jìn)行排序的結(jié)構(gòu)。與在表 中搜索所有的行相比，索引用指針 指向存儲(chǔ)在表中指定列的數(shù)據(jù)值，然后根據(jù)指定的次序排列這些指針，有助于更快地獲取信息。通常情 況下 ，只有當(dāng)經(jīng)常查詢索引列中的數(shù)據(jù)時(shí) ，才需要在表上創(chuàng)建索引。索引將占用磁盤空間，并且影響數(shù) 據(jù)更新的速度。但是在多數(shù)情況下 ，索引所帶來的數(shù)據(jù)檢索速度優(yōu)勢(shì)大大超過它的不足之處。

2. B+樹在數(shù)據(jù)庫(kù)索引中的應(yīng)用

目前大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)及文件系統(tǒng)都采用B-Tree或其變種B+Tree作為索引結(jié)構(gòu)

1)在數(shù)據(jù)庫(kù)索引的應(yīng)用

在數(shù)據(jù)庫(kù)索引的應(yīng)用中，B+樹按照下列方式進(jìn)行組織 ：

① 葉結(jié)點(diǎn)的組織方式 。B+樹的查找鍵 是數(shù)據(jù)文件的主鍵 ，且索引是稠密的。也就是說 ，葉結(jié)點(diǎn) 中為數(shù)據(jù)文件的第一個(gè)記錄設(shè)有一個(gè)鍵、指針對(duì) ，該數(shù)據(jù)文件可以按主鍵排序，也可以不按主鍵排序 ;數(shù)據(jù)文件按主鍵排序，且 B +樹是稀疏索引 ， 在葉結(jié)點(diǎn)中為數(shù)據(jù)文件的每一個(gè)塊設(shè)有一個(gè)鍵、指針對(duì) ;數(shù)據(jù)文件不按鍵屬性排序 ，且該屬性是 B +樹 的查找鍵 ， 葉結(jié)點(diǎn)中為數(shù)據(jù)文件里出現(xiàn)的每個(gè)屬性K設(shè)有一個(gè)鍵 、 指針對(duì) ， 其中指針執(zhí)行排序鍵值為 K的 記錄中的第一個(gè)。

② 非葉結(jié)點(diǎn) 的組織方式。B+樹 中的非葉結(jié)點(diǎn)形成 了葉結(jié)點(diǎn)上的一個(gè)多級(jí)稀疏索引。 每個(gè)非葉結(jié)點(diǎn)中至少有ceil( m/2 ) 個(gè)指針 ， 至多有 m 個(gè)指針 。

2)B+樹索引的插入和刪除

①在向數(shù)據(jù)庫(kù)中插入新的數(shù)據(jù)時(shí)，同時(shí)也需要向數(shù)據(jù)庫(kù)索引中插入相應(yīng)的索引鍵值 ，則需要向 B+樹 中插入新的鍵值。即上面我們提到的B-樹插入算法。

②當(dāng)從數(shù)據(jù)庫(kù)中刪除數(shù)據(jù)時(shí)，同時(shí)也需要從數(shù)據(jù)庫(kù)索引中刪除相應(yīng)的索引鍵值 ，則需要從 B+樹 中刪 除該鍵值 。即B-樹刪除算法

為什么使用B-Tree(B+Tree)

二叉查找樹進(jìn)化品種的紅黑樹等數(shù)據(jù)結(jié)構(gòu)也可以用來實(shí)現(xiàn)索引，但是文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)普遍采用B-/+Tree作為索引結(jié)構(gòu)。

一般來說，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)的磁盤上。這樣的話，索引查找過程中就要產(chǎn)生磁盤I/O消耗，相對(duì)于內(nèi)存存取，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)。為什么使用B-/+Tree，還跟磁盤存取原理有關(guān)。

局部性原理與磁盤預(yù)讀

由于存儲(chǔ)介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：

當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。由于磁盤順序讀取的效率很高(不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間)，因此對(duì)于具有局部性的程序來說，預(yù)讀可以提高I/O效率。

預(yù)讀的長(zhǎng)度一般為頁(yè)(page)的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁(yè)(在許多操作系統(tǒng)中，頁(yè)得大小通常為4k)，主存和磁盤以頁(yè)為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁(yè)異常，此時(shí)系統(tǒng)會(huì)向磁盤發(fā)出讀盤信號(hào)，磁盤會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁(yè)或幾頁(yè)載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行。

我們上面分析B-/+Tree檢索一次最多需要訪問節(jié)點(diǎn)：

h =

數(shù)據(jù)庫(kù)系統(tǒng)巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的，在實(shí)際實(shí)現(xiàn)B- Tree還需要使用如下技巧：

每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的，就實(shí)現(xiàn)了一個(gè)node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O(根節(jié)點(diǎn)常駐內(nèi)存)，漸進(jìn)復(fù)雜度為O(h)=O(logmN)。一般實(shí)際應(yīng)用中，m是非常大的數(shù)字，通常超過100，因此h非常小(通常不超過3)。

綜上所述，用B-Tree作為索引結(jié)構(gòu)效率是非常高的。

而紅黑樹這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)(父子)物理上可能很遠(yuǎn)，無法利用局部性，所以紅黑樹的I/O漸進(jìn)復(fù)雜度也為O(h)，效率明顯比B-Tree差很多。

MySQL的B-Tree索引(技術(shù)上說B+Tree)

在 MySQL 中，主要有四種類型的索引，分別為： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我們主要分析B-Tree 索引。

B-Tree 索引是 MySQL 數(shù)據(jù)庫(kù)中使用最為頻繁的索引類型，除了 Archive 存儲(chǔ)引擎之外的其他所有的存儲(chǔ)引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引，而且只支持索引單個(gè) AUTO_INCREMENT 列。

不僅僅在 MySQL 中是如此，實(shí)際上在其他的很多數(shù)據(jù)庫(kù)管理系統(tǒng)中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因?yàn)?B-Tree 索引的存儲(chǔ)結(jié)構(gòu)在數(shù)據(jù)庫(kù)的數(shù)據(jù)檢索中有非常優(yōu)異的表現(xiàn)。

一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結(jié)構(gòu)來存儲(chǔ)的，也就是所有實(shí)際需要的數(shù)據(jù)都存放于 Tree 的 Leaf Node(葉子節(jié)點(diǎn)) ，而且到任何一個(gè) Leaf Node 的最短路徑的長(zhǎng)度都是完全相同的，所以我們大家都稱之為 B-Tree 索引。當(dāng)然，可能各種數(shù)據(jù)庫(kù)(或 MySQL 的各種存儲(chǔ)引擎)在存放自己的 B-Tree 索引的時(shí)候會(huì)對(duì)存儲(chǔ)結(jié)構(gòu)稍作改造。如 Innodb 存儲(chǔ)引擎的 B-Tree 索引實(shí)際使用的存儲(chǔ)結(jié)構(gòu)實(shí)際上是 B+Tree，也就是在 B-Tree 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上做了很小的改造，在每一個(gè)Leaf Node 上面出了存放索引鍵的相關(guān)信息之外，還存儲(chǔ)了指向與該 Leaf Node 相鄰的后一個(gè) LeafNode 的指針信息(增加了順序訪問指針)，這主要是為了加快檢索多個(gè)相鄰 Leaf Node 的效率考慮。

下面主要討論MyISAM和InnoDB兩個(gè)存儲(chǔ)引擎的索引實(shí)現(xiàn)方式：

1. MyISAM索引實(shí)現(xiàn)：

1)主鍵索引：

MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。下圖是MyISAM主鍵索引的原理圖：