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

是哈希表吗？

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

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

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

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

什么是B树？

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

如下图

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

什么是B+树？

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

如下图

1.B+树的每个结点里可以有N个值，并且在分成N个区间；

2.B树的每个结点的值不能重复出现，B+树则可能重复出现（父元素的值在子元素中会以最大值或者最小值的形式出现）。

3.子叶中各结点是一链表的形式连接起来的，便于范围查找

4.子叶是全集数据（每条记录完整关联到子叶上即可），而非子叶是只需要保存索引（目录）即可，非子叶占用空间相比于子叶这种完整数据集合占用的空间要小的多，就可以放在内存中缓存，查询就进一步减少了硬盘IO。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/124342.html