第五章 索引与算法

InnoDB存储引擎支持的常见索引：
B+树索引，全文索引，哈希索引

B+树索引能找到的只是被查找数据行所在的页，然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。

数据结构与算法：

二分查找法：
将记录按有序化（递增或者递减）排列，在查找过程中次啊用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果找到的元素值小于该中点原属，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。

二叉查找树和平衡二叉树：
B+树是通过二叉查找树，再由平衡二叉树，B树演化而来。

二叉查找树：在二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。

平衡二叉树：首先符合二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为1。平衡二叉树的查找性能是比较高的，但不是最高的，只是接近高性能。最好的性能需要建立一棵最优二叉树，但是最优二叉树的建立和维护需要大量的操作，因此，用户一般只需要建立一棵平衡二叉树即可。

维护一棵平衡二叉树的成本也很高，当插入新的节点时，经常需要一次或者多次左旋/右旋才能得到新的平衡二叉树。不过，平衡二叉树多用于内存结构对象中，因此维护的开销相对较小。

B+树：

B+树是为磁盘或其他直接存取辅助设备涉及的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。

B+树的插入操作：

Leaf Page未满+Index未满：

直接将记录插入到叶子节点

Leaf Page满+Index未满：
1>拆分LeafPage

2>将中间的节点放入到Index Page中

3>小于中间节点的记录放在左边

4>大于或等于中间节点的记录放右边

LeafPage满+Index满：

1>拆分LeafPage

2>小于中间节点的记录放左边

3>大于或者等于中间节点的记录放右边

4>拆分Index Page

5>小于中间节点的记录放左边

6>大于中间节点的记录放右边

B+树的删除操作：
叶子节点小于填充因子（NO）+中间系欸但小于填充因子（NO）：直接将记录从叶子节点删除，如果该节点还是Index Page的节点，用该节点的右节点代替

叶子节点小于填充因子（yes）+中间系欸但小于填充因子（NO）：合并叶子节点和它的兄弟节点，同时更新Index Page

叶子节点小于填充因子（yes）+中间系欸但小于填充因子（yes）：

1>合并叶子节点和它的兄弟节点

2>更新Index Page

3>合并Index Page和它的兄弟节点

B+树索引：

B+树索引就是B+树在数据库中的实现。但是B+索引在数据库中有一个特点是高扇出性，所以，在数据库中，B+树的高度一般都在2~4层，也就是说查找某一键值的行记录时最多只需要2~4次IO。当前一般的机械磁盘每秒至少可以做100次IO,2~4次的IO意味着查询时间只需0.0.2~0.04秒。

数据库的B+树索引可以分为聚集索引和辅助索引，内部都是B+树的，即高度平衡的，叶子节点存放着所有的数据。不同的是，叶子节点存放的是否是一整行的信息。

聚集索引：
聚集索引就是按照每张表的主键构造一棵B+树，同时叶子系欸但中存放的即为整张表的行为记录数据，也将聚集索引的叶子节点成为数据页。同B+树数据结构 一样，每个数据页都是通过一个双向链表进行链接。

实际的数据页只能按照一棵B+树进行排序，因此每张表只能拥有一个聚集索引。

很多资料中提到聚集索引按照顺序物理地存储数据。但是想一想，如果这样，则维护成本显得非常之高。所以，聚集索引的存储并不是物理上连续的，而是逻辑上连续的。

1.页通过双向链表链接，页按照主键的顺序排序

2.每个页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。

聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户要查询的数据。

辅助索引：也成为非聚集索引。叶子节点并不包含行记录的全部数据。叶子节点除了包含键值之外，每个叶子节点中的索引行还包含了一个书签。该书签用来告诉InnoDB存储引擎哪里可以找到于索引相对应的行数据。由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。
非聚集索引的键值在逻辑上也是连续的，但是表中的数据在存储介质上的物理顺序是不一致的，即记录的逻辑顺序和实际存储的物理顺序没有任何联系。索引的记录节点有一个数据指针指向真正的数据存储位置。

辅助索引的存在并不影响数据再聚集索引中的组织，因此每张表可以又多个辅助索引。通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。

B+树索引的分裂：

Cardinality值：
对于性别，地区，类型等字段，可取值范围很小，成为地选择性，不适合添加B+树索引；如果某个个字段的取值范围很广，机会没有重复，即属于高选择性，则使用B+树所以是最合适的。

可以通过show index from tablename结果中的列Cardinality来观察，这个字段标识索引中不重复记录数量的预估值。Cardinality/n_rows_in_table应尽可能地接近1，这样就适合建B+树索引。

InnoDB存储引擎的Cardinality统计：

在生产环境中，索引的更新操作可能是非常频繁的，如果每次索引发生操作时就对其进行Cardinality的统计，统计Cardinality会给数据库带来很大的负担，所以，数据库对于Cardinality的统计都是通过采样（Sample）的方法来完成的。

InnoDB存储引擎内部对更新Cardinality信息的策略为：

1>表中1/16的数据已经发生变化

2>stat_modified_counter>2000000000

InnoDB存储引擎内部是怎样进行Cardinality信息的统计和更新操作的？

1>取得B+树索引中叶子节点的数量，记为A

2>随机取得B+树索引中的8个叶子节点。统计每个页不同记录的个数，即为P1,P2,....,P8.

3>根据采样信息给出Cardinality的预估值：Cardinality=(P1+P2+...+P8)*A/8

在InnoDB1.2版本之前，运行sql语句analyze table,show table status,show index以及访问information_schema架构下的表tables和statistics时会导致InnoDB存储引擎去重新计算索引的Cardinality的值。在InnoDB之后，innodb_stats_on_metadata参数默认为off，运行上边的sql语句不会强制更新Cardinality值。

B+树索引的使用：

联合索引：何时需要使用联合索引呢？

联合索引也是一棵B+树，不同的是联合缩影的键值的数量不是1，而是大于等于2。当where条件中是多个的时候，可以使用联合索引。另外，联合索引的第二个好处是已经对第二个键值进行了排序处理，可以避免多一次的排序操作，因为索引本身在叶子节点已经排序了。

覆盖索引：

InnoDB存储引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的好处是：辅助索引不包括整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

explain中的Extra字段为Using Index说明就是使用了覆盖索引。

优化器选择不适用索引的情况：

多发生于范围查找，Join链接操作等情况下。

可以使用Force Index来强制使用某个索引。

索引提示：

以下两种情况可能需要用到Index Hint:

1>MySQL数据库的优化器错误地选择了某个索引，导致SQL语句运行的很慢。这种情况在最新的MySQL数据库版本中非常非常少见。优化器在绝大部分情况下工作的都非常有效和正确。这时有经验的DBA或者开发人员可以强制优化器使用某个索引，以此来提高SQL运行速度。

2>某个SQL语句可以选择的索引非常多，这时优化器选择执行计划时间的开销可能会大于SQL语句本身。例如，优化分析Range本身就是比较耗时的操作。这时，DBA或者开发人员分析最优的索引选择，通过Index Hint来强制使优化器不进行各个执行路径的分析，直接选择指定的索引来完查询。

哈希算法：

哈希算法时一种常见算法，时间复杂度为O(1)。哈希表也称散列表，由直接寻址表改进而来。

全文索引：