資料結構與演算法
資料庫與檔案系統的索引常使用 B 樹（包含 B+ 樹）而非二元搜尋樹，其主要原因為下列何者？
- A1個節點存放多個鍵使樹變矮，每讀取1次節點就能大幅縮小範圍，因此能減少從磁碟等裝置讀取區塊的次數
- B每個節點只存放1個鍵，因此比較次數比二元搜尋樹少
- C插入時不需要調整形狀，因此實作比二元搜尋樹簡單
查看答案與解析
正確答案：A. 1個節點存放多個鍵使樹變矮，每讀取1次節點就能大幅縮小範圍，因此能減少從磁碟等裝置讀取區塊的次數
磁碟與 SSD 即使只需要1位元組，也以數 KB 的區塊為單位讀取，因此減少讀取次數很重要。B 樹在1個節點（1個區塊）中存放數百個鍵，每讀取1次節點就能分成數百個分支，例如即使有1億筆資料，也只要3～4層就能到達目標資料。插入或刪除使節點溢出時就分割，變少時就合併，讓所有樹葉保持相同深度。二元搜尋樹在1億筆時至少需要約27層，若每層都讀取不同的區塊就會變慢。
- A. 正確。增加分支數使樹變矮，以減少區塊的讀取次數。
- B. 1個節點存放多個鍵正是 B 樹的特徵。
- C. B 樹也會以節點的分割與合併調整形狀，讓所有樹葉保持相同深度。