MySQL|索引
如何理解索引
索引的目的
我们可以将索引类比为字典、目录
在海量数据的查询时，我们可以借助原先生成并维护的索引，将每一次不同的复杂查询都以一种相同的查询顺序（模式）来进行
在使用索引时，本质上是通过不断地缩小想要获得的数据的范围来筛选出最终的结果，将随机的复杂查询目的数据，变成顺序的查询流程
磁盘 IO 与预读原理
在开始讨论索引设计之前，我们需要对计算机（操作系统）针对磁盘 IO 操作读取数据的优化有所了解
对于磁盘 IO 操作，实际上相比于直接访存获取数据而言是很慢的。大概一次 IO 的耗时，是访存的 10w 倍左右
因此计算机的操作系统会在一次 IO 操作读取数据时，不光光是读取指定地址的磁盘数据，而是读取这一地址附近的所有数据。（因为一般来说当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到）
这一地址附近的所有数据我们称之为页(page)，具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO
B+树索引
数据结构
在B+树中，叶子节点和非叶子节点有着明显的存储行为区别
- 非叶子节点不会存储真实数据，只会存储区间的左右端点数据（指引搜索方向的数据项），以及指针
- 只有叶子节点会存储实际的数据
例如上图中，磁盘上并未存储17和35这两个数据，实际存储的数据只有最下面一排叶子节点的数据，例如3、5、9等
索引的查找过程
例如查找29号数据，那么首先会在第一次IO，将磁盘块1加载到内存
然后发现29介于17与35之间，于是通过P2指针，得到磁盘块3的地址，将磁盘块3加载到内存，这是第二次IO
之后基于磁盘块3的数据（内存处理），发现29在26和30的中间，于是通过磁盘块3的P2指针，得到磁盘块8的地址，将磁盘块8加载到内存，这是第三次IO
之后基于磁盘块8的数据（内存处理），得到了29这条数据，查找结束，一共进行了3次磁盘IO操作
3层的B+树在实际的应用场景离可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的
如果没有索引，扫描所有数据项，每一个数据项都要发生一次磁盘IO，那么百万级别的数据中查找总共需要百万次的IO