iT邦幫忙

2024 iThome 鐵人賽

DAY 15
0
Software Development

我獨自升級之資料庫從入門到中階系列 第 15

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

  • 分享至 

  • xImage
  •  

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


上一篇
Day14 select 經歷了哪些-執行sql階段
下一篇
Day16 索引1
系列文
我獨自升級之資料庫從入門到中階20
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言