<data structure> 關於avl-tree與b-tree

[Murphy Chen]

作者 tmg (大斜妖刀雪崩土石流) 看板 Database
標題 Re: 關於avl-tree與b-tree
時間 Thu Oct 9 05:17:48 2003
────────────────────────────[←離開] [PgUp] [PgDn]

※ 引述《cuteamber (安寶)》之銘言：
> AVL-Tree與B-Tree兩種樹狀結構，請問既然兩者都是Tree，那為什麼AVL-Tree
> 比較不適合用在資料庫的儲存結構上？為什麼B-Tree比較適合用在資料庫的儲
> 存結構上？為什麼B-Tree還要進一步改良成為B+-Tree？
> 我這學期才開始學習資料庫，所以這個問題對我有點難，在收尋網站上都是英文，
> 對我來說又更難了.........希望曾各位高手能為我解答。謝謝！

在作 disk I/O 時，一次讀一整塊 block，與分成多次一小塊一小塊的小 block
即使所讀的 byte 數相同，前者的效率比後者高很多

而由於 B-Tree (B+ tree, B* tree... etc.)
比較扁平，每個 node 所承載的資訊量較多
當作搜尋/插入/刪除時，所需 traversal node 的個數比較少
換句話說，會動用到的 disk I/O 次數少
（所付出的代價是，在每個 node 裡頭要花較多的步驟，
但做這些事只須 memory access，與 disk I/O 相比，速度快非常多）
所以，整體效率會比 AVL tree 或 RB tree 來得高

當然，如果不牽涉到 disk I/O，而只是使用 memory access 的話
B-Tree (B+ tree, B* tree... etc.) 就佔不到任何便宜了