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

一、B+樹的特征

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

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

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

二、B+樹的插入

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

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

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

三、為什么B+樹比B樹更適合數據庫索引

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

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

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

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

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

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

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