數據結構與算法分析筆記——B樹
B樹
AVL樹的特徵是，通過在插入或刪除時的微調，使得整個樹中任意節點的左子樹和右子樹之間的高度差不超過1。這樣的結果是，整棵樹的高度不至於太高。那麼，如果我們想要得到一棵更低的樹？該如何呢？合理的設想是增加每個節點的子節點數，比如說，把每個節點的子節點樹從2增加到3或5，樹的高度就會降得更低。這就是B樹的由來。把一棵M階B樹和二叉樹進行比較，有以下不同：
二叉樹中，每個節點最多有兩個子樹，而B樹中，每個節點最多有M個子樹。二叉樹中，每個節點中都存儲著一項數據，而B樹中，真正在數據都存儲在樹葉節點上，中間節點只存儲幫助找到相應樹葉的索引關鍵值。對M階B樹來說，每個中間節點如果有k個子樹，則會存儲k-1個關鍵值。每個樹葉節點中會包含L/2 到 L個數據項，每個節點中的數據項或關鍵值都和其父節點中的關鍵值存在某種關聯關係，以便於搜索。二叉樹中，樹葉節點的深度可能會相差1到2，而B樹中，每個樹葉節點都在同一層階上。比如說，如下就是一棵二叉樹到B樹的轉換：
直觀的就可以看到，B樹比二叉樹更加的矮胖。也就是說，在最壞的情況下，B樹的查找是要比二叉樹快的。但是，由於B樹所有數據都存在樹葉上，所以，二叉樹有可能直接在根節點就找到要找的數據，而B樹，則仍需要通過不斷索引，找到要找的樹葉。也就是，在查詢上來說，B樹比二叉樹更加的均衡。在插入和刪除來說，B樹必然要比二叉樹更加複雜一些。
B樹的意義——減少磁碟訪問次數
用插入和刪除時的效率來換取查詢時的平衡，B樹這樣做是否值得？我們知道，B樹這種數據結構，在資料庫、ES等許多數據存儲中間件中都有使用。所以，我們可以猜測，B樹是有意義的，且意義重大。假設現在有足夠多的數據，使得它們無法全部放到計算機的內存中，那麼，它們就必然要存儲到磁碟上。這時候，要讀取數據，就必然要去讀取磁碟。當程序涉及到磁碟IO的時候，由於磁碟讀取的時間是遠大於內存指令執行時間的，計算機每秒大約可以進行120次磁碟訪問，卻可以執行大約5億條指令。所以，這個時候，程序的運行時間就不再取決於程序表面的複雜度，而在於程序讀取磁碟的次數。B樹就剛剛好符合這樣的需求。內存中有一棵高度為n的B樹，其樹葉上，存儲的都是數據在磁碟中位置，那麼，通過若干的指令和一次磁碟訪問，就可以找到數據。又假如由於數據更多了，那麼，我們可以考慮把n和n-1層都放在磁碟中，這樣，需要的磁碟訪問次數就是2。
B樹的實現
這裡，我們只是討論B樹的某種可能的實現，以幫助我們更深入的理解B樹這種數據結構的內存含義。
關鍵值如何取
關鍵值如何取，一種可能的方式是根據子節點的值的最大值或最小值來界定。比如某個節點包含了兩個關鍵值，2和6，那麼，它就應該有三個子節點，n1,n2和n3。且有n1上的數據一定小於2，n2上的數據一定大於等於2且小於6，n3上的數據一定大於等於6。那麼，有同學可能會問，大於6的都在n3上嗎？當然不是，比如該節點向右有一個兄弟節點，也包含兩個關鍵值，10和14，並有三個子節點，n4，n5和n6。那麼，n3上的數據就應該是大於6且小於10。大於10的數據將會放到n4,n5或n6上。以上這種關鍵值的取法，適用於要存放的數據項有一個可以轉化為數字的關鍵屬性。事實上，關鍵值的取法還可以更靈活些，比如說，要存放的數據項有一個可以轉化為一個英語單詞的關鍵屬性。那麼，我們可以設計出一棵如下的B樹：
第一層用於劃分單詞的長度，某長度上的單詞較少，可以和其它合併到一起。以下若干層用於確定單詞第1到第n個字母。那麼，要尋找apple這個單詞對應的數據項，可能的索引線就會是：5 -> a -> p -> p -> l -> e -> apple。根據要存放的數據項的特徵，還可以設計出更複雜的B樹出來，總之，我們的目的就是不害怕程序的相對複雜，就是要達到減少磁碟訪問次數的目的。當然了，這樣設計出來的B樹，可能已經不是一個普通的B樹了，它可能已經具備了B樹的某些變體的特質。
最少數據項的意義
前面提到，一個M階B樹，要求所有中間節點的兒子樹在 M/2到M之間，所有樹葉節點上的數據項在 L/2到L之間。最大值的設定容易理解，最小值的設定是為什麼呢？這是為了避免B樹的退化。如果不設定最小值，在某些極端情況下，某個B樹中的節點的子樹可能會變成2，1甚至0，也就是說，該子節點退化成了一棵二叉樹。所以，最小值要求你在這樣極端情況下，要去重新規劃節點及節點中的關鍵值，以保持B樹不退化。
B+樹
B+樹相比B樹來說，主要有以下不同：
B樹中，中間節點的關鍵值總比子節點少1，而B+樹中，關鍵值和子節點樹相等。B+樹中，樹葉節點會構建成一個鍊表。也就是說，不通過其父節點，可以直接按序遍歷所有的樹葉節點。B+樹相比B樹而言，最大的一個優勢在就在於，查範圍內批量數據時，只需要確定第一條數據所在的樹葉節點，就可以通過鍊表直接定位到下一個樹葉節點。所以，資料庫採用的不是基本的B樹，而是B+樹。