天天看點

Mysql索引為什麼使用B+樹

為什麼不适用二叉平衡樹(AVL樹,紅黑樹)

Mysql索引為什麼使用B+樹

1.二叉平衡樹每個節點有兩個子節點,這意味着樹的高度更高,IO次數更多

2.查詢效率不穩定,如果要查詢的資料在葉子節點,需要進行多次IO

3.磁盤IO是以頁為機關的,一頁=4k,如果使用二叉平衡樹,每個節點隻存儲兩個子節點的引用(兩路),也就是一次IO操作隻加載了兩個自己子節點的引用,太浪費了

是以要使用多路平衡樹

為什麼不使用B樹

B+樹與B樹的差別:InnoDB中索引的實作采用的是B+樹。B+樹是B樹的變種。B+樹非葉子節點不存儲資料隻存儲索引,在相同資料量下,B+樹高度更低,且B+樹葉子節點之間組成一個連結清單,便于周遊查詢

B樹:

Mysql索引為什麼使用B+樹

我有一壺酒

足以慰風塵

盡傾江海裡

贈飲天下人

繼續閱讀