MySQL索引结构

除数据之外，数据库中还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，以实现高级查询算法。这种数据结构就是索引。

表数据record，在硬盘上存储到 user.idb（尾缀为innodb）文件中，称为表空间，实际上被拆分成多个数据页，每份大小16K（这是一个硬性规定，在MySQL5.6版本之前无法更改，之后通过innodb_page_size 参数修改）。是Innodb磁盘管理的最小单位

分支主题

16K的页空间是一个参考值，只能在MySQL实例初始化之前配置，不可在之后修改，实际上可以根据不同的业务场景和硬件支持进行调整。遵循原则：1、单行略小于页大小的一半，避免发生行溢出现象（保证每个页块中至少有两行数据，避免因数据行过大导致B+树退化）；2、合理根据IO性能设置页大小。默认的16K适合各种工作负载，过大影响写到磁盘块（系统的文件读取大小为4K）被重写未更改的数量和数据争用；过小索引的溢出现象会较为严重。CPU取数据为页的整数倍放入内存

页中的页目录维护了页内的record记录的查询结构，是基于二分查找实现的，查找效率从O(n)变成O(logn)

页空间大小有限，为了加速搜索，我们在每个页空间选出ID最小的record，组成新的record，放到新生成的页中，新生成的页大小和结构没有什么区别，大小还是16K。形成了上下级的关系，叶子节点的页层级（page level）是0。注意页号并不是连续的，在磁盘中也不一定是顺序存放的

https://mp.weixin.qq.com/s?__biz=Mzg5NDY2MDk4Mw==&mid=2247488133&idx=1&sn=169533ab3946f2f018478d6d2abf532a&scene=21#wechat_redirect

页空间

B+树的节点分为两种，一种是叶子节点，存放具体的数据record，另外一种是单纯的主键+页号组成的数据的非叶子节点。假设非叶子节点的数据行数量为X，叶子节点的record数量为Y，层数为Z，则计算公式为：X的（Z-1）次方*Y

一般来说，二叉树是指一个节点可以散发出两个新节点。m叉树的一个节点可以指向m个新节点，指向新节点的操作叫做扇出。B+树的扇出可以维持到1280左右

Y的计算，是叶子节点中可以再次容纳数据行record的数量。按照索引节点相似的算法，假设每条数据是1K，所以Y=15

综上，假设Z=3层，则计算公式为1280的3-1次方乘以15， = 1280*1280*15≈2.5kw的数据。这就是我们单表建议2-3千万数据的由来。三层数据对应三次磁盘IO，也比较合理

通过上面的计算，我们发现单表容量的大小跟数据行record的大小也是相关的，小表也能在控制层数的情况下实现容量的限制突破并且不影响查询性能

B+树承载记录数量计算

B树也叫B-树，相对于B+树，B树在叶子节点和非叶子节点都存放数据，并且最底层叶子节点没有指针相连接。B+树只有在最底层叶子节点中存放，并且有指针相连接

B树容量计算：假设页空间还是16K，就算排除节点之间的指针（大概只有4bit）和页属性只有15K空间存放record，则计算公式变成了：15的1次方+15的2次方...15的z次方，z即层数，每层的数据存放之和就是页块的倍数，而每层都是15的指数。即为一个等比数列

对比得知，要保存2kw的数据，z至少等于6，查询最坏的情况下要访问6个页，对应6次磁盘IO。数据页的扇出也明显变少。因此B+树比B树更加适合作为索引

B树的优势：访问更加迅速，根节点数据只需一次查询，而B+树至少需要两次（不考虑覆盖索引的情况）

和B树的对比

1、为什么用树而不是hash表：hash表不支持按区间快速查找数据，且无法进行排序操作且无法避免全表扫描（Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，hash冲突时还需要轮询链表）

2、什么是最左匹配原则：MySQL创建的复合索引会对最左边（也就是第一个字段）进行ASCII排序再拼接，保证了最左边的索引是绝对有序的，而第二个字段是无序的，也就无法用到索引了。这就是MySQL非常强调联合索引的最左匹配原则的原因

为了存储一行行的数据，我们将链表相连，未避免查询时间复杂度变成O(n)，我们提取部分节点联接起来，再构建出新的链表。多加几层，查询范围都会减半。这种通过牺牲空间换取时间提升了查询性能，时间复杂度是O(lgn)

B+树和跳表都在最下面一层包含了所有的数据，并且都是顺序的，适合范围查询

B+树是多叉树结构，每个结点都是一个16k的数据页，能存放较多索引信息，所以扇出很高。三层左右就可以存储2kw左右的数据。也就是说查询一次数据，如果这些数据页都在磁盘里，那么最多需要查询三次磁盘IO。

跳表是链表结构，一条数据一个结点，如果最底层要存放2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在2的24次方左右，所以，跳表大概高度在24层左右。最坏情况下，这24层数据会分散在不同的数据页里，也即是查一次数据会经历24次磁盘IO

而针对写操作，B+树需要拆分合并索引数据页，跳表则独立插入，并根据随机函数（保证二分法）确定层数，没有旋转和维持平衡的开销，因此跳表的写入性能会比B+树要好

3、为什么选用B+树而不是跳表

4、B+树与redis跳表的对比：redis 是纯纯的内存数据库，进行读写数据都是操作内存，跟磁盘没啥关系，因此也不存在磁盘IO了，所以层高就不再是跳表的劣势了。B+树是有一系列合并拆分操作的，换成红黑树或者其他AVL树的话也是各种旋转，目的也是为了保持树的平衡。而跳表插入数据时，只需要随机一下，就知道自己要不要往上加索引，根本不用考虑前后结点的感受，也就少了旋转平衡的开销

5、innodb页大小为什么16k：在操作系统的文件管理系统中进行一次io读写，默认读取的大小为4kb（一页）。又因为局部性原理，操作系统会将命中的页周围的三块页一同加载进innodb的缓存池中，因此innnodb缓存池中页的大小为16kb

稠密索引：每一条记录，对应一个索引字段，访问速度非常块，但是维护成本大。根据索引字段不一样，有候选键索引和非候选键索引之分。

稀疏索引：并没有每条记录，建立了索引字段，而是把记录分为若干个块，为每个块建立一条索引字段。要求索引字段是按顺序排序的，否则无法有效索引

6、稠密与稀疏索引

索引常见问题

B+树叶子节点和非叶子节点大小都是16K，且数据结构一致，区别在于叶子节点存放的是真实数据，非叶子节点存放是是主键和下一个页的地址

B+树一般只需要2-3层，由于其高扇出，三层就能维持2KW以上的数据，一次查询最多1-3次磁盘IO，总体性能较为优异和稳定

存储同样数量级的数据，B树对比B+树需要的层级更高，因为磁盘IO也更多。

索引总结

MySQL索引