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

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

是哈希表吗？

        不是，虽然哈希表的增删查改速度都很快，但对于 大于、小于、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。