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

一、B+樹的特征

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

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

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

二、B+樹的插入

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

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

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

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

1、B+樹的磁盤讀寫代價更低

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

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

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

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

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

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