上一章節介紹的BST可以有很讚的Θ(LogN)效能做到insert和contains方法，但其實有個很實際的問題我們還沒有想到，那就是如果當我們今天要加入的元素是越來越大的，那我們的BST會變成以下左側的spindly tree：

你可能想問，這種情況實際嗎？會真的碰到嗎～其實非常常見，比如我們要紀錄timestamp的話，就肯定是會越來越大的是不是？

該如何解決這個問題呢？前人的智慧想到了一個妙招，既然問題是出在tree最底下的node(稱為leaf node)，那我就不要讓他長出新的一層葉子吧！如果有新加的node進來，我就把他塞在同一個葉子中：

我知道你可能會覺得，這點子也太智障了，如果我一直加入新的元素，不就會變成下面這樣：

阿如果塞進的元素數量遠大於其他node的數量時，我的BST效能就變成O(N)了啊！

沒有錯，你想得到前人們也想得到，所以應變的措施就是限定node最高乘載量，假若多餘最高乘載量時，把中間的一個元素往上推，並且讓上方元素多出一個node，以下是承載量L = 3的範例：

這邊我們假設規定是把中間偏左的元素往上推：

↓

推上去後發現違規了，16會比17還小，不符合BST的規範：

↓

所以16就會順理成章的可以放在15跟17中間，變成3個child node：

以上的示範就是B-Tree，而根據L的不同，會有不同的稱呼，像上面L=3就會被稱為2-3Tree。

那假設我們遇到root node被塞到大於L該怎麼辦呢？

很直覺的，就是一樣把中間偏左的元素往上，它就變成新的root node：

可以觀察到B-Tree很有趣的一個特點，就是樹永遠是bushy的，也就是最底層的node永遠都是滿的！這就是我們一開始探討的spindly tree的問題，在B-Tree中就被解決了～

B-Tree的兩個特徵：

1. 所有的leaf node都會有同樣的height，亦即bushy的意思
2. 非leaf node的節點若包含k個元素，那就一定會有k+1個child node

下面來分析B-Tree的runtime：

先來分析height的問題，對於height來說，最糟的情況就是每個node都只塞了一個元素，造成height增長的比較快，也就是$log_2{N}$；而最佳的情況就是每個node都塞了L個元素，height增長最慢，就會是$log_{L+1}{N}$：

再來分析運行contains方法的runtime，我們要尋找目標元素時，最多要搜尋H+1次(包括root的比較)，而當找到node後，在node中尋找時最多會尋找L次，所以就會是O(HL)，而剛剛分析過的height帶進來，就會是O(L logN)，又L是常數可忽略，最終就是O(logN)。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License