关于索引详见：MySQL索引
说明
索引的本质是数据结构，本文讲解mysql 索引原理与B+Tree
顺序访问
顺序访问是在表中进行 全表扫描，从头到尾逐行遍历，直到找到符合条件的数据。
优点：实现比较简单
缺点：当表中有大量数据的时候，效率非常低下
二叉树
使用 二叉树 存储 age 列的数据，查找速度会快很多，如下：
缺点
根据 数据结构：二叉排序树（二叉查找树） 的缺点，需要用到 平衡二叉树
平衡二叉树
缺点
根据上文的缺点，需要用到 红黑树
红黑树
详见 数据结构：红黑树
缺点
根据上文的缺点，需要用到 B树
B树
详见 数据结构：B-树
缺点
根据上文的缺点，需要用到 B+树
B+树
详见 数据结构：B+树
B+树索引
上面 user 表数据，放在了 user.ibd 文件中
数据页
在表中，每行记录看起来是挨在一起的。但在 user.ibd 文件中，他们被分成很多小份的 数据页，每份大小 16k，如下：
数据页的组成
页头
整个页 16k，较小，但表中一行行的数据多，一页肯定放不下，所以会分开放到很多页里。为了唯一标识具体是哪一页，给每一页编上号码，即： 页号（其实是一个表空间的地址偏移量）。
同时为了把这些数据页给关联起来，于是引入了前后指针，用于指向前后的页。这些都被加到了页头里。
校验码
向某数据页写数据时，写一半断电，会造成数据损坏。
所以为了保证数据页的正确性，引入了校验码。这个被加到了页尾。
保存行记录
剩下的空间，才是用来放一行行的数据。
页目录
而record如果行数特别多的话，进入到页内时挨个遍历，效率也不太行，所以为这些数据生成了一个 页目录，通过 二分查找 的方式将查找效率从 O(n) 变成 O(lgn)。
从页到索引
笨方法
如果想查一行记录，可以读取每一页，再把里面的 数据 读取出来挨个判断是不是要找的。
行数量小的时候，这么操作也没啥问题。
缺点
行数量大了，性能就慢了
加索引
于是为了加速搜索，在每个数据页里选出 主键id最小的记录，而且只需要它们的 主键id和所在页的页号。组成新的记录，放入到一个新生成的一个数据页中，这个新数据页跟之前的页结构没啥区别，而且大小还是16k。
但为了跟之前的数据页进行区分。数据页里加入了 页层级（page level）的信息，从 0 开始往上算。于是页与页之间就有了 上下层级的概念，就像下面这样：
页跟页之间看起来就像是一棵倒过来的树了，即：B+树 索引。
最下面那一层，page level 为0，也就是所谓的叶子结点，其余都叫非叶子结点。
三层B+树
上面展示的是两层的树，如果数据变多了，我们还可以再通过类似的方法，再往上构建一层。就成了三层的树。
那现在我们就可以通过这样一棵B+树加速查询
查询
查找数据5
先从顶层页的开始，记录里包含了主键id和页号（页地址）。
看下图黄色的箭头，向左最小id是
1，向右最小id是7。那id=5的数据如果存在，那必定在 左边 箭头。于是顺着的记录的页地址就到了6号数据页里再判断
id=5大于4，所以肯定在 右边 的数据页里，于是加载105号数据页。在数据页里找到id=5的数据行，完成查询。
注意：页号并不是连续的，它们在磁盘里也不一定是挨在一起的。
优点
由于此处树的高度是 3，所以查询了 3个页，那么最多需要经历 3次磁盘IO查询
B+树最大记录数量
参考
https://blog.csdn.net/nandao158/article/details/114065093
https://mp.weixin.qq.com/s/XX_NkIIf_PLyU4IE6lEEYQ