2.索引的数据结构是什么?
2.1 可以是二叉搜索树或者红黑树吗?
不可以
二叉搜索树的平均查找效率是O(logN)- 如果数据很多的话,二叉搜索树最多俩个分支,所以
树的深度会很大,查找效率其实不高- 如果是查找范围的时候还需要对二叉搜索树进行中序遍历 (因为二叉搜索树中序遍历是有序序列) 又不是很高效
O(N)
2.2 可以是哈希表吗?
不可以
- 如果是处理相等情况,哈希表很高效
- 但是
哈希表不可以处理其他逻辑,比如范围查找> >= < <= between and - 因为哈希的查找是把key带入哈希函数得到下标,再根据下标取对应的链表,再去遍历链表比较key是否相等,无法进行范围查找
2.3 可以是B树吗?
- 本质可以,但为了更高的效率不选它
B树与二叉树差异：
- 为了结点不是2叉而是
N叉- 为了结点不是存储一个数据,而是可能存储多个数据
每个节点存储数据的个数和该节点的度是有关系的 度=存储数据的个数+1- 此时在B树上查找就是一个N分查找,效率比二叉树还高
- 由于每个及节点存储了多个数据,每个节点又有多个度,所以和二叉树相比,B树的高度会低很多,查找起来效率一会高一下.而且简单的范围查找会容易一些.
在整个数据量的条件一定的情况下，N叉搜索树的高度 一定比 二叉搜索树要低。
在数据库中使用的这个多叉树，又不太一样，是一个很特殊的树，我们称为 B+ 树。
【B+ 树 是 数据库中最常见的数据结构】
注意！数据库有很多种，每个数据库底层又支持多种存储引擎
这些存储引擎实现了数据库具体按照什么结构来存储的程序。
那么就意味着 每个存储引擎 存储数据的结构 可能都不一样，背后的索引数据结构可能也不同。
所以，这里面可能会有很多种多叉树来去表示这里的数据结构。
只是 B+ 树 是 最常用的一种数据结构。
那么，B+ 树 又是什么样子的？
想要 理解 B+ 树，需要先理解它的前身 B 树（ B-树：这个是B树的另一种写法，而不是B减树）
2.4 可以是B+树吗?
与B-树相比的差异：
每一层的元素之间都链接在一起数据(表的一行记录)只存在叶子节点上,非叶子节点只保存一些辅助查找的边界信息- 查询任一条记录都比较平均,不会出现效率差异很大的情况
- 不需要额外进行中序遍历,遍历叶子节点就是中序结果,所以处理范围查找很高效
- 叶子放在磁盘上,非叶子放在内存中,减少了访问磁盘的次数,查找也就更高效了,而且索引在内存中实际开销有不高
- 索引引起的效果就是加快查找效率, 减慢插入删除修改的效率 (因为需要同步调整索引结果)
- 索引也会占用额外空间(本质上使用空间换取时间)
- 给具体表中某列加索引的时候,加在主键的索引和加在其他列的索引是截然不同的.
- 主键索引的叶子结点value存的是表的一行完整数据, 其他索引的叶子节点value只存的是主键的信息(如id)
因为B树 是 B+树的前身，那么B+树想对比B树又做出了那些改变？
疑问：为什么B+树这么去构建？
你可以这么认为 B+ 树 就是为了 数据库索引量身打造的！！！！
- 使用B+树进行查找的时候，整体IO次数也是比较少的。
所有的查询最终多会落在叶子结点上，每次查询的 IO 次数都是差不多的，故查询的速度是稳定的，相差不大。叶子结点用链表链接之后，非常适合进行范围查找所有的数据存储（数据又称载荷）都是放到叶子结点上的。也就是说非叶子结点中只需要保存key值就可以了。因此非叶子节点整体占用空间较小，甚至可以加载到内存中。（一旦能够全部放在内存里，此时硬盘上的IO次数几乎就为零了）
例如：
找到 大于等于5，且小于等于 11 的值。
所有的数据存储（数据又称载荷）都是放到叶子结点上的。也就是说非叶子结点中只需要保存key值就可以了。因此非叶子节点整体占用空间较小，甚至可以加载到内存中。（一旦能够全部放在内存里，此时硬盘上的IO次数几乎就为零了）
总结
