資料結構與演算法分析筆記——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+樹。