Day15 為什麼使用 B+Tree 當作儲存結構

資料庫索引的儲存資料結構考量

1. 資料存在 Array 然後使用 二分搜尋，這樣搜尋效率O(logN)，但是插入時候需要把所有元素向後移動一位，這對硬碟會有大量的IO，效能很差。因此我們不能用這種線性結構在硬碟上存資料！其次就是在陣列內使用二分查找，每次查找都要不斷計算中間的位置。

2. Binary Search Tree(BST)：非線性且天然適合二分查找的數據結構，但他存在一個問題 - 極端情況會將二元樹退化成LinkedList(例如插入[1,2,3,4,5]這個例子，這樣搜尋速度從O(logN)變成O(N)，除了搜尋的效率變差，最重要的是，每訪問一個節點，就是對硬碟做一次IO，硬碟IO非常慢(相對於記憶體)，所以BST也不夠適合當資料庫的結構。

3. 平衡二元搜尋樹(AVL Tree)：BST之上多一個條件 - 每個節點的左子樹和右子樹的高度差不能超過1。這種會維持自平衡的AVL Tree，搜尋就可以維持在O(logn)。另一種是使用紅黑樹，也會自平衡。但這兩種樹，只要插入的節點多，免不了樹高還是會增長，對於很慢的硬碟IO，解法還是不夠漂亮。那如果二元樹改成多元樹呢？

4. B+Tree(其實還有BTree，但我們直接介紹B+Tree)：把二元改成多元的自平衡樹，並且
   (1). 如果是叢集索引(PK)，就把索引+資料放在葉子節點
   (2). 如果是二級索引，就把PK放在葉子結點裡，查到PK後回表再去查叢集索引的樹。
   葉子節點之間互相使用雙向鍊結串連，這樣對於範圍查找效率很好。最大的改善就是由於是多元樹，高度可以壓縮在最低(4層內)。

下一篇來講索引

微推廣一下自己的社群xD

有關Side Project Taiwan的簡介

Side Project Taiwan 的宗旨是藉由Side Project開發來成就自我，透過持續學習和合作，共同推動技術和專業的發展。我們相信每一個參與者，無論是什麼專業，都能在這個社群中找到屬於自己的成長空間。

歡迎所有對Side Project開發有興趣的人加入我們，可以是有點子來找夥伴，也可以是來尋找有興趣的Side >Project加入，邀請大家一同打造一個充滿活力且有意義的技術社群！

Discord頻道連結：https://sideproj.tw/dc