B+樹，索引樹

引言

時隔一年，我又想起當初看資料庫時，看到的B+樹，就是資料庫的索引使用的數據結構。再整理一下，看看自己沒有忘記很多吧。

B+樹之前，先來看一下二叉查找樹（1,2,3,4,5,6,7）

恩，差不多就長這樣。誠然，在二叉查找樹中查找某個元素是很快速的，二分查找嘛。但想想資料庫查找數據的場景：

select * from user where id > 10，顯然，對於這種查找區間來說，二叉查找樹並不高效。那麼B+樹是如何解決這個問題的呢？

試想一下，區間查找比較高效的數據結構是什麼？數組，只要找到id為10的元素下標，那麼之後的所有就都符合了。

那麼把上面修改一下，讓二叉查找樹樹的葉子節點直接指向數組的下標不就好了嘛。修改後結構如下：

這時，如果想找select * from user where id > 2 and id < 5, 那麼，直接找到2的下標，然後向後遍歷，到第一個>=5的值出現停止，之間是滿足條件的數據。沒錯，這就是B+樹。

這個結構是怎麼想出來的我不知道啊，但是我今天突然發現，他的存儲方式和跳錶十分之像啊。莫非是受到了跳錶的啟發？亦或是跳錶受到了B+樹的啟發？咱也不知道。

很好，B+樹整明白了，新的問題出現了。如果資料庫使用這種數據結構存儲，全部放到記憶體中肯定是不現實的，勢必要將其存儲到硬碟中，待查找時再到文件中讀取。但如果放到文件中，勢必會造成IO的緩慢，每次讀取節點都訪問文件，要是樹到高度很誇張的話，光IO就要耗盡耐心了。

既然如此，那就降低IO好了，增加樹每一層的節點數量，也就是二叉樹變成n叉樹（也確實是這麼做的）。

算一下，如果是3叉樹，高度為3（這個高度為索引樹的高度），可索引的數組長度為：（3^4=81）；如果是5叉樹，高度為3，可索引數組長度為：（5^4=625）；如果是100叉樹，高度為3，可索引長度為：（100^4=1億）。索引1億的數據量，高度也只有3，意味著只要進行3此IO就可以定位到。完美。

那樹進行分叉過多，是不是在每個節點搜索子節點的效率下降了？這裡可以再使用一些查找演算法降低時間複雜度。

以上就是我回憶的內容了，感覺並沒有什麼晦澀的，大部分是重新回憶了一遍。但是，溫故而知新嘛。不知點新怎麼好意思寫出來。一下就是我最近才曉得的了。

那肯定不是越多越好啊，要是一層就把所有數據都存儲了，要他還有什麼用，根本沒有起到快速定位的作用。

但我想說的並不是這。我們知道，作業系統在讀取磁碟中的數據時，是按照頁來讀取和管理的，一頁大小為4kb。當讀取數據時，如果大小超過4kb，就會觸發多次IO。4kb的大小，其實對於存儲節點已經很大了。也就是說，我們每個節點的大小最好是<=4kb，否則就會觸發多次IO。

但是，節點在更新時，勢必會導致其大小改變。如何保證n叉樹始終為n叉樹呢？

添加節點

其實很簡單，多了就拆唄。如果節點超出大小，就拆分成兩個節點。但拆分後父節點不就多了么。那就父節點在拆，一直拆到根節點為止。如果根節點在超出大小，那就再拆，整個新的根節點出來。

刪除節點

其實，刪除節點不做處理也不會影響節點大小超出限制。但是，長此以往，可能會導致某些節點元素過少，嚴重影響查詢效率。那麼，如果節點內元素的數量小於n/2，就把相鄰的兩個節點合併為一個節點。那要是合併後元素數量超出大小呢？再拆唄。