mysql索引内部实现与算法
innodb支持的常见索引：
哈希索引（自适应的）
B(balance)+树索引：构造类似二叉树，根据键值快速找到数据
原理：B+树索引通过找到被查数据所在的页，然后将页读入内存，再在内存中进行查找，最后得到查找的数据。
二分查找法(折半查找法)：查找一组有序的记录数组中的某一记录
基本思想：将记录按有序化（递增或者递减）排列，先以有序数列中的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。
平衡二叉树：
二叉查找树
说明：图中中数字代表每个节点的键值，二叉查找树中，左子树的键值总是小于根的键值
平衡二叉树定义：首先符合二叉查找树的定义，然后任何节点的左右两个子树的高度最大差为1
B+树
B+树由B树和索引顺序访问方法演化而来
B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，所有记录节点都是按照键值的大小顺序存放在同一层的叶节点中，各叶节点指针进行连接。
B+树的插入操作
B+树的插入必须保证插入后叶节点中的记录依然排序，
插入B+树的三种情况
第一种情况，往图中插入28，leaf page和index page都没有满，直接插入
第二种情况，往图中插入70，leaf page满了，index page没有满
说明：采用旋转操作使得其减少一次页的拆分操作
第三种情况，在图中插入95，leaf page和index page都满了
说明：B+树为了保持平衡，对新插入的键值可能需要大量的拆分页操作，但是B+树主要用于磁盘，我们应该尽可能减少页的拆分，可以通过旋转功能（leaf page已经满了，但是左右兄弟节点没有满）
B+树的删除操作
B+树使用填充因子来控制树的删除变化，50%是填充因子可设的最小资。同样必须保证删除后叶节点中的记录依然排序。
删除B+树（根据填充因子的变化来衡量）的三种情况
在图中删除70
在图中删除25，此时25的兄弟节点的28更新到page index中
在图中删除60，此时填充因子小于50%，需要做合并操作
B+树索引
B+树索引本质是在B+树在数据库中的实现 特点：扇出性
数据库中B+树索引分为：聚集索引（clustered index）、辅助聚集索引（secondary index）
索引组织表：表中数据按照主键顺序存放
堆表：按照插入数据顺序存放，堆表上的索引都是非聚集的，且堆表没有主键
聚集索引(每张表只有一个):按照每张表的主键构造一棵B+树，且叶节点存放着整张表的行记录数据，所以聚集索引的叶节点也成了数据页，
辅助聚集索引的叶节点上存放的仅仅是键值以及指向数据页的偏移量，不是一个完整行记录
聚集索引的存储在物理上是不连续的，在逻辑上是连续的：1.页通过双向链表链接，页按照主键的顺序排序；2.每个页中的记录也是通过双向链表进行维护，物理存储上可以同样不按照主键存储
聚集索引对于主键的排序查找和范围查找速度非常快
辅助索引：叶节点包含键值，且每个叶级别的索引行还包含一个书签（相应行数据的聚集索引）
辅助索引和聚集索引的关系图
说明：辅助索引的存在不影响数据在聚集索引中的组织，所以每张表可以有多个辅助索引
通过辅助索引来寻找数据时过程：innodb会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。
B+树索引的管理
索引的创建和删除的方法：alter table；create /drop index
创建主键索引过程：先创建一张新的临时表，然后将数据导入临时表，删除原表，再把临时表重名为原来的表名
创建辅助索引过程：在创建过程中不需要重建表，只会对表加上一个S锁，速度极快。
通过show index from table_name可以查看表中索引的信息
说明：
table：索引所在的表名
Non_unique:非唯一索引，primary key是0
Key_name:索引的名称
Seq_in_index:索引中该列的位置
Column_name：索引的列
Collation:列以什么方式存储在索引中，B+树索引总是A，即排序；如果使用了heap存储引擎，且建立了hash索引，就会显示NULL，因为hash通过hash桶来存放索引数据，而不是对数据进行排序
Cardinality:表示索引中唯一值的数目的估计值，Cardinality/表的行数 尽可能接近1，太小则需要重建该索引
Sub_part:是否是列的部分被索引，如只索引某一列的前多少字符，如果索引整个列，则该字段为NULL
packed：关键字如何被压缩。没有被压缩则为NULL
NULL：是否索引的列含有null值，
Index_type:索引的类型，innodb只支持B+索引
comment:注释
B+树索引的使用
当访问高选择性字段并从表中取出很少一部分行时，就需要对这个字段添加B+树索引
注：当取出数据量超过表中数据的20%，优化器就不会使用索引，而是进行全表的扫表。且预估的返回行数的值是不准确的
顺序读、随机读、预读取
顺序读（sequntial read）：顺序地读取磁盘上的块（block）
随机读（random read）：访问的块不是连续的，需要磁盘的磁头不断移动
预读取（read ahead）：通过一次IO请求将多个页预读取到缓冲池中
随机预读取（random read ahead）：当一个区（64个连续页）中13个页也在缓冲区中，并在LRU列表的前端（即页是被频繁访问），则innodb会将这个区剩余的所有页预读到缓冲区
线性预读取（linear read ahead）：基于缓冲池中页的模式，而不是数量。如果一个区中的24个页都被顺序访问了，则innodb会读取下一个区的所有页
innodb_read_ahead_threshold参数：表示一个区中的多少页被顺序访问时，innodb才启用预读取。默认值为56，即当一个区中的56个页被顺序访问时，则预读取下个区的所有页
联合索引：还是一棵B+树，不同的是联合索引的键值的数量不是1，而是大于等于2
译者介绍：家华，从事mysqlDBA的工作，记录自己对mysql的一些总结