B+Tree索引原理
什么是索引？
索引是一种数据结构，具体表现在查找算法上。
索引目的
提高查询效率
【类比字典和借书】
如果要查“mysql”这个单词，我们肯定需要定位到m字母，然后从下往下找到y字母，再找到剩下的sql。如果没有索引，那么你可能需要把所有单词看一遍才能找到你想要的。
去图书馆借书也是一样，如果你要借某一本书，一定是先找到对应的分类科目，再找到对应的编号，这是生活中活生生的例子，通用索引，可以加快查询速度，快速定位。
数据结构——树
树
二叉树
每个节点最多含有两个子树的树称为二叉树。
二叉查找树ADT Tree
左子树的键值小于根的键值，右子树的键值大于根的键值。
平衡二叉树AVL Tree
在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。
BTree
BTree也称为平衡多路查找树
B-Tree是为磁盘等外存储设备设计的一种平衡查找树。
B+Tree
B+Tree是在B-Tree基础上的一种优化
- 非叶子结点只存储键值信息，不存储数据
- 所有的叶子结点都有一个链指针
- 记录都存放在叶子结点中
1569143297523
MySQL默认使用B+Tree索引
索引本身也很大，所以存储在磁盘中,需要加载到内存中执行。
故：索引结构优劣标准：磁盘I/O次数
BTree是为了充分利用磁盘预读功能而创建出来的一种数据结构。
局部性原理和磁盘预读
局部性原理：当一个数据被用到，其附近的数据很可能会马上用到 磁盘预读：由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入主存。
为什么平衡二叉树无法利用磁盘预读功能而BTree可以？
平衡二叉树也称为红黑数，在逻辑上是平衡二叉树，但是在物理存储上使用的是数组，逻辑上相近的节点可能在物理上相差很远。
BTree如何利用磁盘预读功能？
将节点大小设为等于一个页，BTree新建节点时，也是按照页为单位申请，同时计算机存储分配也是按页对齐，那么一个节点只需一次IO就可以读取全部节点数据。
【如果节点大小和BTree大小不对齐，那么同一页节点可能需要两次IO读取】
综上所述，用B-Tree作为索引结构效率是非常高的。
为什么B+Tree比BTree更适合作为索引结构?
BTree解决了磁盘IO的问题但没有解决元素遍历复杂的问题。
B+Tree的叶子节点用链指针相连，极大提高区间访问速度。【比如查询50到100的记录，查出50后，顺着指针遍历即可】
为什么不使用Hash索引而使用B+Tree索引？
Hash索引本质上是Hash表，是一种KV键值对的存储结构。
无法提高区间访问速度。
B+Tree的叶子结点可以存哪些东西？
可能是整行数据，也可能是主键的值。
前者被称为聚簇索引，后者称为非聚簇索引。
聚簇索引更快！！！
为什么？？？聚簇索引已经查到整行数据了，而非聚簇索引还可能根据主键值再进行查询一次。
例外：覆盖索引——数据直接从索引中取得。