MySQL 索引原理
索引是以字段为键、记录为值的 B+ 搜索树。
一、索引的减少 I/O 设计
从硬盘搜索读取查询记录时，由于一次硬盘读取数据到内存的时间是内存里操作数据时间的 10 万倍，MySQL 通过索引数据结构的设计减少了查询记录的硬盘 I/O 的次数。
1. 读取量
保持硬盘单次最大读取量（页）最大量地进行读取，以减少读取 I/O 次数。每个 B+ 搜索树节点的存储空间是一个页，即对应每次读取完一个 B+ 搜索树节点的总页存储空间的内容量。
2. 搜索树
2.1 方向
在搜索树中，查询时会避免遍历地每次往正确范围、正向增长搜索到概率的方向进行搜索，直到最后搜索到也会精确匹配。
2.2 有序
搜索树结构维护了记录值以字段键的有序性，支持以字段的范围查询记录与以字段的排序记录。
对比哈希表： 哈希表虽然能实现一次硬盘读取就可 O(1) 地查询到记录，但只能精确匹配，内部是以哈希函数维护的无序数组，无法范围查询，也无法进行排序。
3. 多叉分支
在一次读取的一个节点中放多个排布搜索对象分多叉，能一次更多对象的排布完、一次更多对象的搜索完、一次搜索接往到更加细致确定的范围区间里来。
3.1 B 树
键值对单位存储
键值对合空间如果很小，节点可以直接大量存储键值对，每个节点排布海量 N 个键值对 N+1 次方地向下分支排布搜索数据来完成海量键值对数据的入树的排布。
弊端：
- 存储少 -> 排布少 - 分支少 - 树高 - I/O 高
但在数据库中，一个值记录的空间很大，一个键字段的空间很小，键值对的合空间很大：
一个节点一个页的存储量放不了多几个键值对排布分叉的，每个节点能存储下来的排布数据少向下分支少向下搜索的区间广，需要往下分支很多次才可分布排完数据，树的高度会很高，处在叶子节点的大部分键值对要硬盘从顶层多次读取搜索到底层才可搜索到，硬盘 I/O 总体会很高。
记录在全节点 -> 不稳定
作为查询搜索的结果的键值对里的值记录，与键一块直接存储在出现的树节点中，少部分的在非叶子节点的键值对可以少量 I/O 地往下读取搜索到，大部分的在叶子节点的键值对需要大量 I/O 地读取到底层，查询的时间开销不稳定。
3.2 B+ 树
键与值分开存储
B+ 树针对数据库里值记录空间很大，一个搜索树节点无法存下过多个键值对去海量分叉排布，将键与值分开存储，键在非叶子节点搜索，值在叶子节点对应。
3.2.1 非叶子 - 搜索字段
3.2.1.1 海量分叉
3.2.1.1.1 最大式
非叶子搜索阶段每个非叶子节点只放无记录值对应的海量键字段，一个节点一个页就可最多放多达 1600 个键字段地大量排布搜索数据细致划出排往范围地搜索。
3.2.1.1.2 最快式
内存中操作数据的速度虽然快，但一次从硬盘读取到内存的数据如果处理的单位个数过多，一时间内内存里也无法快速比较完个数过多的数据，所以每个节点放 1000 个键字段以 1000 的幂次方向下分支排布存储搜索的数据，3 层对应 3 次硬盘读取就可排查地搜索完分支排布到亿级的字段量。
3.2.1.2 缓存内存
3.2.1.2.1 字段总量小
非叶子节点内的亿级总记录个数的字段量，由于字段的空间很小，能确保所有全记录对应的字段总空间是很小的，况且缓存只对非叶子节点并未对分支到最后一层的叶子节点的记录里的字段量进行缓存，所以非叶子节点里也不会有所有记录个数对应的总字段量那么多，非叶子节点字段总空间很小可以缓存到内存中的。
3.2.1.2.2 时间复杂度
首次查询： 非叶子节点字段量在首次查询时 B+ 搜索树高度次硬盘读取从硬盘把此搜索树的所有非叶子节点全部读取加载到缓存中存放。
后续查询： 在后续查询时，非叶子节点的字段数据都已加载在缓存内存中有不用再硬盘读取直接继续在缓存中对字段进行搜索常数时间，然后搜索出指定叶子节点后再对存储在硬盘的叶子节点键值对硬盘读取一次固定一次硬盘 I/O 的常数时间，时间复杂度也就成了 O(1)。
