Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

淺談 B+樹

看,未來 2021-09-27 11:18:43 阅读数:43 评论数:0 点赞数:0 收藏数:0

目前常見的主要的三種存儲引擎是:哈希、B+樹、LSM樹。LSM下次再說,hash講過了。

沒有什麼B-樹,那是 B-tree,國內一直翻譯成B-樹,其實就是B樹。

B樹我也不想說了,因為已經被昇級過了,叫B+樹。

下圖來自 小灰的算法之旅,懂得人自然就懂了:
在這裏插入圖片描述


對比一下B樹:
在這裏插入圖片描述

這個是B樹。


B+樹對於B樹的改進

1、所有數據都在葉子節點。算法更容易理解了。回頭抽空手寫一下B+樹,正好跳錶也要重寫了。

2、底層葉子節點使用鏈錶串起來了。

這第二個改進不可謂不秀。單這麼看自然是不明所以的,但是凡事都要放在上下文中去看,B+樹的上下文對應的就是磁盤IO的索引呐,那如果我要範圍查詢呢?比如說我要上面樹裏面 4-10 的所有數據,B 樹怎麼作為?B+樹怎麼作為?高下立判。


代碼實現

先占個比特置,國慶假期內定會補上。

版权声明
本文为[看,未來]所创,转载请带上原文链接,感谢

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领