漫画：什么是B+树？

朱雀 2023-05-28 14:27 244阅读 0赞

在上一篇漫画中，我们介绍了B-树的原理和应用，没看过的小伙伴们可以点击下面的链接：

[漫画：什么是B-树？][B-]

这一次我们来介绍B+树。

—————————————————

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

**一个m阶的B树具有如下几个特征：**

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

![format_png 4][]

**一个m阶的B+树具有如下几个特征：**

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

![format_png 17][]

![format_png 18][]

B-树中的卫星数据（Satellite Information）：

![format_png 19][]

![format_png 20][]

B+树中的卫星数据（Satellite Information）：

![format_png 21][]

需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。

![format_png 22][]

![format_png 23][]

![format_png 24][]

第一次磁盘IO：

![format_png 25][]

第二次磁盘IO：

![format_png 26][]

第三次磁盘IO：

![format_png 27][]

![format_png 28][]

![format_png 29][]

![format_png 30][]

![format_png 31][]

![format_png 32][]

![format_png 33][]

**B-树的范围查找过程**

自顶向下，查找到范围的下限（3）：

![format_png 34][]

中序遍历到元素6：

![format_png 35][]

中序遍历到元素8：

![format_png 36][]

中序遍历到元素9：

![format_png 37][]

中序遍历到元素11，遍历结束：

![format_png 38][]

![format_png 39][]

![format_png 40][]

**B+树的范围查找过程**

自顶向下，查找到范围的下限（3）：

![format_png 41][]

通过链表指针，遍历到元素6, 8：

![format_png 42][]

通过链表指针，遍历到元素9, 11，遍历结束：

![format_png 43][]

![format_png 44][]

![format_png 45][]

![format_png 46][]

![format_png 47][]

**B+树的特征：**

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

**B+树的优势：**

1.单一节点存储更多的元素，使得查询的IO次数更少。

2.所有查询都要查找到叶子节点，查询性能稳定。

3.所有叶子节点形成有序链表，便于范围查询。

![format_png 48][]

—————END—————

[B-]: http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653190965&idx=1&sn=53f78fa037386f85531832cd5322d2a0&chksm=8c9909efbbee80f90512f0c36356c31cc74c388c46388dc2317d43c8f8597298f233ca9c29e9&scene=21#wechat_redirect
[format_png]: /images/20230528/5dfe507996d1464dbb802a5143a611b2.png
[format_png 1]: /images/20230528/0ca343a49770491e923d09a08c795083.png
[format_png 2]: /images/20230528/f4246a26f0d14143ad2d7133fb9ba35b.png
[format_png 3]: /images/20230528/7152e640704e42d1ba6f75c0a873612f.png
[format_png 4]: /images/20230528/08e2e7f813d841af91ea43eecae1c7c4.png
[format_png 5]: /images/20230528/b089b13bc95b4d5e8c1982f569b3f8b8.png
[format_png 6]: /images/20230528/776ff8dbcf774557b1260aec8417ad76.png
[format_png 7]: /images/20230528/716de27512f7483c88090372d376a8ab.png
[format_png 8]: /images/20230528/4c781c3ee36e419889994db90a839ac0.png
[format_png 9]: /images/20230528/c32fa12ff8b3444da5395dbb9bc5f853.png
[format_png 10]: /images/20230528/c0d1c0e6cf354980be91369e1a02aae5.png
[format_png 11]: /images/20230528/eb8e8f31f6c64fccbec5704055445308.png
[format_png 12]: /images/20230528/7467b604dbc94696b20cce167f406596.png
[format_png 13]: /images/20230528/59ef0caee68a48b39cc2fc9648413b63.png
[format_png 14]: /images/20230528/3720d6c0fc7944bf819ca7cb67fd327d.png
[format_png 15]: /images/20230528/df69018c3b084971b1a13018e789724f.png
[format_png 16]: /images/20230528/8997e6e4b83d4cb3a6d33ab613a41ede.png
[format_png 17]: /images/20230528/acb6ce26a176411a9ed4ccaf00b52607.png
[format_png 18]: /images/20230528/6083183a892e40bf8928f35d86d84bca.png
[format_png 19]: /images/20230528/f309a0907b2d48179d496c0d6097d7db.png
[format_png 20]: /images/20230528/5c3744fb70ef40d491d70f6d2ed85112.png
[format_png 21]: /images/20230528/5913cb48e09d4c59b91cc8ff730f1424.png
[format_png 22]: /images/20230528/494f17ecfb3f4782a8337f2926a00195.png
[format_png 23]: /images/20230528/7c311aca792a4a848b269274e1d8819c.png
[format_png 24]: /images/20230528/484b1cf3c38b4ddba6a4a20a6e4b1565.png
[format_png 25]: /images/20230528/10cdd8acca3740e58e36e857e384aa32.png
[format_png 26]: /images/20230528/abac7a2df4f84d7a91d20e9225d007fb.png
[format_png 27]: /images/20230528/ac1ff1dd77644394a848c091f38ed176.png
[format_png 28]: /images/20230528/285fdfc31ad94b7090598ac938446532.png
[format_png 29]: /images/20230528/4a20fdabf8a34361992e8b870c2de011.png
[format_png 30]: /images/20230528/3cc7cfc5151642e393c266fcf7cb8c9b.png
[format_png 31]: /images/20230528/00a96909257c47e6aa4fb90d2da8a348.png
[format_png 32]: /images/20230528/f35479ded69246d7b33afae18490e202.png
[format_png 33]: /images/20230528/514f5ba0816a4936a664bc0036191d6a.png
[format_png 34]: /images/20230528/9de58a7d641648cc8a8bd8968d6fbb03.png
[format_png 35]: /images/20230528/2b3ced6346304249999e5550bf087f7b.png
[format_png 36]: /images/20230528/a18dec8aff8a455b9be56b2fe78d6661.png
[format_png 37]: /images/20230528/8c91bc3716a1479a9a47153e46ac155b.png
[format_png 38]: /images/20230528/525bef5d2b464f1eb7c0daeb45e59e88.png
[format_png 39]: /images/20230528/bb06252a90b144ef8033f66b58b9ad48.png
[format_png 40]: /images/20230528/883969a3f4514f63a043550f7be583e9.png
[format_png 41]: /images/20230528/0693a633a2e94f09b4f65c88e4d6c4d3.png
[format_png 42]: /images/20230528/746dd864c450451f8d96a18212383e5b.png
[format_png 43]: /images/20230528/2dc143c8e359401b823f6b8e7b6c83e4.png
[format_png 44]: /images/20230528/056e0abba5244ddca0acb177c3eda8ca.png
[format_png 45]: /images/20230528/108f91b4f0ed43bd9444479ccc313f08.png
[format_png 46]: /images/20230528/193de2770a5c4772a2e7a6f73436ea2b.png
[format_png 47]: /images/20230528/5839f3bb88ba446a9859eed27c3b8498.png
[format_png 48]: /images/20230528/07d72fb6a6c248afad4af37475a48569.png