什么是B+树

骑猪看日落 2024-05-01 16:04 88阅读 0赞

转载自：[伯乐专栏作者/玻璃猫，微信公众号 - 梦见 漫画：什么是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.所有叶子节点形成有序链表，便于范围查询

[- _ _b]: https://www.sohu.com/a/156886901_479559
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMTdhMGM0ZjY3MmIzNGU2NjhhMGNkMmViMjE0YzExN2RfdGgucG5n?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYzU2MTU1YzIxMzFlNDViMGJmNjlmOWFlNmNiYTA1NmVfdGgucG5n?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMTY0Y2UzZDI1MDRjNGQ2Mzk0NWUxMzRjYTY3NTJhMmNfdGgucG5n?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvODkxYWQxOWZiNDI5NGU5MjkzZmRjYTgzZThlMzQ2MTZfdGgucG5n?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvZWI3OTBmMDhhMDJhNGJjYmJjN2NmM2YzZjhhOTVkNGRfdGgucG5n?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvZmY1NzFjZmQ3MmFiNGEwNjhjZTA4NjdiMGU0NTBkZThfdGgucG5n?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvZDQ0MzBlYjVlNWVmNDIwMDhiMWZhY2VjNTE2MzZkYmJfdGgucG5n?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMzU4MDI1ODY3YmUxNGJiOTliZjg4MDZiOThlNzc0ZDlfdGgucG5n?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMDM0YTg2ZDZlMWQ5NGM3OThlNjNhYjE0NDk1NWMwZjZfdGgucG5n?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvODZmNzMyZGQ5MGI3NGJlM2JmOTQ5NDg1OWZhNzhkNjZfdGgucG5n?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMDYxMWZmNWE1MTAzNDYxZTg0M2FiNjI3Zjg4MjE0MTlfdGgucG5n?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYWRhZGE0OTk5ZmRkNDhkNDkzN2Y1ZjE0YzBlYjc3OTJfdGgucG5n?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYWZmZmRhMjE1NzhiNGQ4YTkwY2JkZWE0OTc2ZmI1YjZfdGgucG5n?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMjk1ODNkNDkzNThlNDFmYTljMmZiYzUxNjlmYjdkMTRfdGgucG5n?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMDRlYjEyMGNkMWUwNGQzYTk0YzI0ODJhYmM3ZGViOTZfdGgucG5n?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvM2NlMjhiYTBhMmJkNDI2ZWJlYmFjOTYwM2Y3Mjg2MDNfdGgucG5n?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvM2JkMmI0MjIwYTBmNGQxODg3ZTI5NDNhNzI5YzQwYTFfdGgucG5n?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvNjY0ZTM2YTRkYTBmNDVmY2FmNmUxOGI2OGQzNmEwYjRfdGgucG5n?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvNTE0ZDU4N2ZhNzM3NDY5NzgyMDBhY2EyNTI4MzdhNDRfdGgucG5n?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMzZlZmE2OTU2MWRjNDA0M2ExN2Q1NTAxMzNlMTNhNmNfdGgucG5n?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYzNhNTE5YTlhOWU4NDU2ZDliZTQxZTY5NzA5YmFmYWZfdGgucG5n?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvZDhhZTFiMTRlOWJmNGIxODkwMTQ2ZWI4MDNlZTk3OTVfdGgucG5n?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvN2E1MjYyNGU3YWRkNDAzM2JiNDljM2FhNTYzMmE2ODFfdGgucG5n?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMGFlMWQwOGVjZTFlNGRhZWFjMzczNjFlODZiM2Q2YTZfdGgucG5n?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMzJhZDBlNjIzNzYyNGQ3MThiYjlhNTM0NmUzNzc5MmVfdGgucG5n?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvNjgwODkwNzc4NWI4NGJlMDlkOGM2YjdjOGFjYjVkMmFfdGgucG5n?x-oss-process=image/format,png
[format_png 26]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMDE5M2VlZGYzYTViNDcxMjkzNDBlMmI2YzY1NGVmNzJfdGgucG5n?x-oss-process=image/format,png
[format_png 27]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvNjg1NTNkMzY5YTMwNGQ3OTgxMTZmNDMyMjQ3YzZlM2ZfdGgucG5n?x-oss-process=image/format,png
[format_png 28]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMzgzMDMwMGMxNWJmNDFmOGEyYzhmZGY4ZDE2M2ZhNWJfdGgucG5n?x-oss-process=image/format,png
[format_png 29]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYmFhZWQ5OGQ4ZmNhNGZiOTgwNjQwMDY1MTk1M2Y5MmRfdGgucG5n?x-oss-process=image/format,png
[format_png 30]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvOTlkNTA2NzQ1MWVjNDg2ZGJjY2MzNzYxMWZmMzc0N2NfdGgucG5n?x-oss-process=image/format,png
[format_png 31]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvNzUyMmQyODExYjUzNDBhN2E5YjIyMmJjMTRiYTcyNzZfdGgucG5n?x-oss-process=image/format,png
[format_png 32]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMTY5ZGVmMDgwZThlNDdhNjhmYzRmZGNlMzQ1MTMzN2FfdGgucG5n?x-oss-process=image/format,png
[format_png 33]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvOGRiMWJjNTJhYjJjNDE4ZWI5YTkyZmJiMTE4OWRiOThfdGgucG5n?x-oss-process=image/format,png
[format_png 34]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYmI0MGI3MDAyNDdjNDI1ZjliOWQzNThjNzI2ZDVlNjVfdGgucG5n?x-oss-process=image/format,png
[format_png 35]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMjQ0ZWE2ZWFlZTRhNGUxZDg3YTMzOTY3ZmY2ZWY1ZmZfdGgucG5n?x-oss-process=image/format,png
[format_png 36]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvNjFmNDcyYTU2Zjc4NDBlNzhkZTIzOTAxY2I1ZTg1YjJfdGgucG5n?x-oss-process=image/format,png
[format_png 37]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYTc4ODFlMTY4M2E4NDg2ZmEzOTU2ZDU4NWE5N2JkNmRfdGgucG5n?x-oss-process=image/format,png
[format_png 38]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYzNmYzNjMDk3Y2Y5NGQ0MzljNWQ2OTYyZDJmYjhkNGVfdGgucG5n?x-oss-process=image/format,png
[format_png 39]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMWEzYzhmOTNiZTMyNDlkMjhiMDgxM2Y5ZDBkNWU5OThfdGgucG5n?x-oss-process=image/format,png
[format_png 40]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvODBlZmYxYTExY2YyNDQ1OGE1Y2Y4MGI4MjFkMzY1Y2RfdGgucG5n?x-oss-process=image/format,png
[format_png 41]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvYzBlZjRkMjJjZWRmNDNjYzhkMjE3MzJkMjdmOWJlM2VfdGgucG5n?x-oss-process=image/format,png
[format_png 42]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMDA1Nzc3ZDgxYWIyNDdjMjgxZjhhMWI0YmM2YjM0NjFfdGgucG5n?x-oss-process=image/format,png
[format_png 43]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvZTk3MmU0N2IyYzU1NGY3ODllMDJlOTBiMjZhOGI1NDNfdGgucG5n?x-oss-process=image/format,png
[format_png 44]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvZmI5Y2U1ZWJhMmY4NDVjN2IzNzhkYTE5MjEwMjk1MTFfdGgucG5n?x-oss-process=image/format,png
[format_png 45]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvMGJhNWMyNTk4NDNhNGQwZThlZjVkMzE4MzYyZjA5N2ZfdGgucG5n?x-oss-process=image/format,png
[format_png 46]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvNDRjZDE0MWVkNTA5NGMwOWExODcwZDA0NDlmOWFhYjdfdGgucG5n?x-oss-process=image/format,png
[format_png 47]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5tcC5zb2h1LmNvbS91cGxvYWQvMjAxNzA3MTMvOWI1NTMwMDE1YjMyNDg0MWE1NzA1MDU3OThjOTM3ZjRfdGgucG5n?x-oss-process=image/format,png