面试：“索引背后的数据结构是什么样的？”，五分钟带你了解“B树，B+树”

痛定思痛。 2024-04-08 10:24 53阅读 0赞

## 索引背后的数据结构是什么样的？ ##

**是哈希表吗？**

不是，虽然哈希表的增删查改速度都很快，但对于 大于、小于、between and...这类比较大小的范围查询可能是不行的；

**会是二叉搜索树、AVL树、红黑树吗？**

二叉搜索树的最坏情况，单枝树最坏情况，时间复杂度为 O(N)，即使是AVL树、红黑树、这种尽可能平衡的二叉搜索树，时间复杂度为O(logN)，当数据库的数据特别多时，这些树的高度也就会非常高（logN），这和比较次数是相关的，如果是在内存中比较，多比较几次倒也无所谓，因为内存的访问速度很快，但如果实在硬盘上进行的，那就要思量一下了~

**所以，程序猿为数据库的索引专门定制了一个数据结构——B+树**

--------------------

## 什么是B树？ ##

要想了解B+树，首先来了解一下什么是B树：

如下图

![caba9847bd614dee85b1497d84430c9d.png][]

> B树是一个N叉搜索树，每个结点可能包含 N - 1 个值，这 N - 1个值就把区间划分成N份，并且每个结点值不能重复出现，这样划分有什么意义呢？就是表示相同元素的数据集合的时候比二叉树的高度小很多，IO次数也降低了很多~

--------------------

## 什么是B+树？ ##

了解完B树，再来看看B+树：

如下图

![0be133a6210040b0a7c724bf0cdd188e.png][]

> 1.B+树的每个结点里可以有N个值，并且在分成N个区间 ；
> 
> 2.B树的每个结点的值不能重复出现，B+树则可能重复出现（父元素的值在子元素中会以最大值或者最小值的形式出现）。
> 
> 3.子叶中各结点是一链表的形式连接起来的，便于范围查找
> 
> 4.子叶是全集数据（每条记录完整关联到子叶上即可），而非子叶是只需要保存索引（目录）即可，非子叶占用空间相比于子叶这种完整数据集合占用的空间要小的多，就可以放在内存中缓存，查询就进一步减少了硬盘IO。

[caba9847bd614dee85b1497d84430c9d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/cb63e7e100a24c3495cd6f2f4460e22d.png
[0be133a6210040b0a7c724bf0cdd188e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c8dca37cb2e5476082ed3d56859b0162.png