B+樹是一種樹數(shù)據(jù)結(jié)構(gòu)，通常用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中，NTFS等都使用B+樹作為數(shù)據(jù)索引。B+樹的特點(diǎn)是能夠保持?jǐn)?shù)據(jù)穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對(duì)數(shù)時(shí)間復(fù)雜度。B+樹元素自底向上插入，這與二叉樹恰好相反。

一、B+樹的特征

1、有m個(gè)子樹的中間節(jié)點(diǎn)包含有m個(gè)元素（B樹中是k-1個(gè)元素），每個(gè)元素不保存數(shù)據(jù)，只用來索引；

2、所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。 (而B 樹的葉子節(jié)點(diǎn)并沒有包括全部需要查找的信息)；

3、所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最小）關(guān)鍵字。 (而B 樹的非終節(jié)點(diǎn)也包含需要查找的有效信息)；

二、B+樹的插入

1、若為空樹，直接插入，此時(shí)也就是根結(jié)點(diǎn)

2、對(duì)于葉子結(jié)點(diǎn)：根據(jù)key找葉子結(jié)點(diǎn)，對(duì)葉子結(jié)點(diǎn)進(jìn)行插入操作。插入后，如果當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)不大于m-1，則插入就結(jié)束。反之將這個(gè)葉子結(jié)點(diǎn)分成左右兩個(gè)葉子結(jié)點(diǎn)進(jìn)行操作，左葉子結(jié)點(diǎn)包含了前m/2個(gè)記錄，右結(jié)點(diǎn)包含剩下的記錄key，將第m/2+1個(gè)記錄的key進(jìn)位到父結(jié)點(diǎn)中（父結(jié)點(diǎn)必須是索引類型結(jié)點(diǎn)），進(jìn)位到父結(jié)點(diǎn)中的key左孩子指針向左結(jié)點(diǎn),右孩子指針向右結(jié)點(diǎn)。

3、針對(duì)索引結(jié)點(diǎn)：如果當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)小于等于m-1，插入結(jié)束。反之將這個(gè)索引類型結(jié)點(diǎn)分成兩個(gè)索引結(jié)點(diǎn)，左索引結(jié)點(diǎn)包含前(m-1)/2個(gè)數(shù)據(jù)，右結(jié)點(diǎn)包含m-(m-1)/2個(gè)數(shù)據(jù)，然后將第m/2個(gè)key父結(jié)點(diǎn)中，進(jìn)位到父結(jié)點(diǎn)的key左孩子指向左結(jié)點(diǎn), 父結(jié)點(diǎn)的key右孩子指向右結(jié)點(diǎn)。

三、為什么B+樹比B樹更適合數(shù)據(jù)庫索引

1、B+樹的磁盤讀寫代價(jià)更低

B+樹的內(nèi)部結(jié)點(diǎn)并沒有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B 樹更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來說IO讀寫次數(shù)也就降低了；

2、B+樹查詢效率更加穩(wěn)定

由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢的路徑長(zhǎng)度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)；

3、B+樹便于范圍查詢（最重要的原因，范圍查找是數(shù)據(jù)庫的常態(tài)）

B樹在提高了IO性能的同時(shí)并沒有解決元素遍歷的我效率低下的問題，正是為了解決這個(gè)問題，B+樹應(yīng)用而生。B+樹只需要去遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷。而且在數(shù)據(jù)庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作或者說效率太低；

以上就是對(duì)B+樹這一數(shù)據(jù)結(jié)構(gòu)的簡(jiǎn)單介紹，我們基本上了解了B+樹的特點(diǎn)和性質(zhì)，知道了B+樹適合數(shù)據(jù)庫索引的原因。從某種意義上來說，B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的B樹的變形樹，因此和B樹也會(huì)有以下相似之處，但我們還是應(yīng)該避免混淆兩者的概念。在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中也有對(duì)B樹的詳細(xì)描述，不知道如何區(qū)分兩者的小伙伴可以去了解一下B樹，然后回顧本文或許就簡(jiǎn)單明了了。