《MySQL技术内幕：InnoDB存储引擎》第五章 索引与算法
5.1 InnoDB存储引擎索引概述
InnoDB支持两种常见的索引
- B+树索引
- 哈希索引（自适应的，会根据表的使用情况自动生成，不能人为干预）
一个常被忽略的问题：
B+树索引并不能找到一个给定键值的具体行，只能找到被查数据所在的页，然后数据库将此页读入内存，再在页中查找最后得到数据。
5.2 二分查找法
每页Page Directory中的槽是按照主键的顺序存放的，对于某一条具体记录的查询是通过对Page Directory进行二分查找得到的。
5.3 平衡二叉树
二叉查找树
制杖二叉查找树
若想最大性能的构造一个二叉查找树，需要这棵树是平衡的 -- 平衡二叉树，或称AVL树，平衡二叉树并不一定是最优二叉树。
维护平衡二叉树必然有一定的开销， 不过多用于内存结构对象中，所以开销相对较小
5.4 B+树
B+树
5.4.1 B+树的插入操作
B+树插入情况
插入28
插入70
插入95
5.4.2 B+树的删除操作
B+树用填充因子（fill factor）来控制树的删除变化，50%是填充因子可设的最小值。
B+树删除
删除70
删除60
5.5 B+树索引
B+索引在数据库中一个特点就是其高扇出性，在数据库中，高度一般都是在2-3层，也就是查询一个数据，最多只需要2-3次IO。
B+树索引可以分为聚集索引（clustered index）和辅助聚集索引（secondary index）。其不同点是，叶节点存放的是否是一整行的信息。
5.5.1 聚集索引
InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一棵B+树，叶节点中存放的整张表的行记录数据，因此也让聚集索引的叶节点成为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树一样，每个数据页都通过一个双向链表来进行链接。
- 聚集索引可以让我们在索引的叶节点上直接找到数据；
- 此外由于定义了数据的逻辑顺序，聚集索引能够特别快的访问针对范围值的查询，查询优化器能够快速发现某一段范围的数据页需要扫描。
- 聚集索引对于主键的排序查找和范围查找速度非常快
5.5.2 辅助索引（非聚集索引）
页级别不包含行的全部数据。叶节点除了包含键值以外，每个叶级别的索引行中还包含了一个书签，该书签用来告诉InnoDB哪里可以找到与索引相对应的行数据，实际上，辅助索引的书签就是聚集索引键。
聚集索引与辅助索引关系
5.5.3 B+树索引的管理
索引创建和删除方式
ALTER TABLE 1
ALTER TABLE 2
CREATE/DROP
目前对于索引的添加或者删除，均为创建一个临时表，把数据导入临时表，删除原表，重命名临时表，所以大表操作索引也会很费时间。
但是InnoDB Plugin开始，支持一种称为快速索引创建方法，当时只限于辅助索引，对于索引的创建，不用重新建表，而是加上一个S锁。删除时，在内部视图更新下，将辅助索引的空间标记为空，并删除MySQL内部视图上对于该表的索引定义即可。
5.6 B+树索引的使用
5.6.1 什么时候使用B+树索引
访问表中很少一部分行时，才有建表必要（高选择性）。而对于取出很多行时，没有必要建立索引。
及时高选择性的字段，但是取出大部分数据，此时不会使用索引（日期范围等情况）
5.6.2 顺序读、随机读与预读取
预读取，通过一次IO将预测会访问的多个页缓存下来
- 随机预读取。一个区中有一部分页被频繁访问，则预读本区整个区。
- 线性预读取。一个区多少页被顺序访问，则预读下个区的所有页。
很尴尬的是，预读取关闭时比开启性能还要好，InnoDB Plugin1.0.4后随机访问的预读取关了，但是线性预读取还是保留了。
当前数据库策略并不适合固态硬盘
5.6.3 辅助索引的优化使用
当辅助索引叶节点有足够数据时（比如只查询主键），数据库会使用辅助索引，但是当对主键order by 或者强制使用聚集索引，就会用回聚集索引
5.6.4 联合索引
对表上多个列做索引，按顺序使用索引列才会命中，因为单独看后面的列，并没有按顺序摆放。
5.7 哈希算法
5.7.1 哈希表
直接寻址表
哈希表
链表法解决碰撞
