产品中心
索引太少，查询效率低；索引太多程序性能受到影响，索引的使用应该贴合实际情况。
Innodb 支持的索引包括：
B+树并不能定位到表上具体的行记录，而是返回该行记录所在的页；最后在内存中根据 slot槽 信息，以及行记录头中的next record 信息进行精确定位。
二分查找只能用来对一组有序的线性数据进行查找，每次取中值，小往前，大往后。时间复杂度 ：log N，如图为对有序数组中的数字48的查找。
二叉查找树指的是，一个二叉树中，都满足：任意节点左子节点比自身小，任意节点右子节点大于自身的二叉树，即为二叉查找树。
普通的二叉树无法保证 O(logN) 的访问时间，因为当极端情况下，它甚至可以退化成链表。
当把一组有序的数据按序构建一个二叉树，那么就得到了一个链表，此时时间复杂度变为：O(N)
平衡二叉树是二叉搜索树，但是它多了一个限制条件：任意节点的两个子节点的树高相差不能超过1。构建二叉树的过程中，如果破坏了这个条件，可以通过适当的旋转来解决。
平衡二叉树保证了时间复杂度为：O(logN)
虽然能保证O(logN) 的访问时间，但是它并不适合用来做数据库索引：
二叉树树高攀升非常快(1024 = 2的10次幂)，当数据量非常巨大时log(N) 也是非常可观的。
其中最糟糕的是，二叉树的叶子节点只能存放一个数据，必定要进行多次的磁盘IO。然而实际应用中相较于CPU的执行指令的时间，频繁读取磁盘将是灾难性的。所以，二叉树并不适合用来做数据库的索引。
对于机械硬盘，其访问时间取决于磁盘转速和磁头移动时间，这都是由机械结构完成的，对比cpu 中执行的电信号指令，速度必定天差地别。<CPU的时钟周期一般以GHz为单位。>
1000万数据，如果使用平衡二叉树（最坏时间界限为 1.44 * logN ），即便不取最坏时间界，按 log(N) 计算最终约为 24，那么说明需要进行 24 次磁盘IO，这显然不行。
【树高为对数值向上取整，例如：log3 = 1.58，树高为2；】
由于平衡二叉树的局限，所以需要引入B+树。
B+树是专为磁盘或其它直接存取辅助设备设计的一种平衡查找树，B+ 树中，所有记录节点都是按键值大小， 顺序存放在同一层的叶子节点上，由各叶子节点指针进行链接。
一颗M阶的B+树需要满足如下的性质：
下列所有定义中的关于两数相除，不能整除时往上取整，而不是丢弃小数位。(案例中推演不等式除外)
1）数据项必须存在叶子节点上
2）非叶节点存贮M-1个关键字以指示搜索方向；关键字 i 代表非叶节点的第i + 1 棵子树中最小的关键字；假设5阶B+树，那么它有 5 – 1 = 4 个关键字。
3）B+树要么只有一个树叶节点作为根节点(没有任何儿子节点)；如果它有儿子节点，它的节点数必须属于集合：{2~M}；
4）除根外，所有非叶节点的儿子节点数必须满足属于集合： { M/2 ，M } ；
5）所有树叶都在相同深度上，且树叶节点的数据项个数必须属于集合：{ L/2 ，L } ；
以下表为例，模拟推演B+树，主键50字节，算上行记录本身消耗空间，假定所有字段总长不超过500字节：
已知所有行记录都会消耗一些字节记录行信息：例如变长字段，行记录头，事务ID，回滚指针等等。
参考下图，平衡二叉树最坏时间界为：1.44 * logN = 25.58 * 1.44 = 36.83；也就是说5000W 数据若使用平衡二叉，树最坏情况下会超过36 次磁盘IO，最少26次磁盘IO。
如图为一颗5 阶普通B+树 (M = 5)，此处每个节点最多5个值（L = 5）; M和L不一定相等，就如上述分析而言: M 和 L视实际情况而定。
哈哈哈画图太麻烦了，我从数据结构与算法分析这本书上拍的照片，机智如我。
这里只讲B+树定义以及参数选取详情，B+树的插入、B+树的删除部分类容不在赘述。
一般B+ 树树高 为2~4 层，也就是查找行记录时一般只需要2 ~ 4 次磁盘IO就能找到行记录所在的页。不论聚集索引还是非聚集索引，内部都是高度平衡的，索引的数据都存放于叶子节点，区别是聚集索引的叶子节点存放了整个行记录数据。
聚集索引的叶子节点存放整行数据，每张表只能拥有一个聚集索引。
辅助索引的叶子节点存储了键值和一个书签，该书签告诉Innodb 存储引擎从哪里可以找到于索引相应的行记录完整数据。<可以认为该书签就是聚集索引的关键字，也就是表的主键>
每张表可以有多个辅助索引
使用辅助索引的缺点是，找到辅助索引存储的书签后，还需要去离散的读聚集索引，才能最终得到完整的行数据。
对于Cardinality的讨论都是基于非聚集索引的，每个非聚集索引都会有一个Cardinality值。
须知并不是所有查询条件中的列都需要加索引；比如：性别、年纪、科目等取值范围小、密集分布的字典量，就不需要建立索引。
Cardinality 表示索引中不重复记录数量的 预估值 ，一般： Cardinality / 表中记录行数 应尽量接近 1；如果非常小，则需要考虑该索引是否应该去掉。(聚集索引中该值必定接近于1，没有讨论价值)。
【 本部分讨论的索引多指辅助索引，对聚集索引的查询一般称为全表扫描。】
联合索引是在表上的多个列上建索引，它也是B+树结构，与单个索引的区别仅是它存在多个列。
如上图所述，键值有序，需要注意的是，如下SQL可以使用该索引：
3).对于范围查询：MMR还支持对键值的拆分，将范围查询拆分为键值对进行批量的数据查询.
ICP优化也从MySQL 5.6 开始支持，它是一种根据索引进行查询的优化方式，它支持对：range、ref、eq_ref、ref_or_null 类型的查询进行优化。
【使用这个过滤的前提是：该过滤条件需要是，索引可以覆盖到的范围】
Index Condition Pushdown工作原理如下：
1)不使用ICP时
（1）当存储引擎读取下一行时，从辅助索引的叶子节点读到相关的行记录，然后使用该记录的书签中的主键引用，以查询完整的行记录返回给数据库层(Server层)。
（2） 数据库层对完整的行记录进行where条件过滤，如果该行数据满足where条件则使用，否则丢弃。
（3）执行第1步，直到读完所有满足条件的数据。
2）使用ICP时，如何进行索引扫描
（1）存储引擎从索引中逐条读取数据……
（2）存储引擎从索引读取数据时，根据索引的key使用where条件过滤，如果该行记录不满足条件，存储引擎将会处理下一条数据（回到上一步）。只有满足查询条件的时候，才会继续去聚集索引中读取完整数据。
（3）最后存储引擎层会将所有满足查询条件数据的完整行记录返回数据库层。
（4）数据库层再继续使用，没有被索引覆盖到的where后的查询条件进行过滤。
到此这篇关于Mysql Innodb存储引擎之索引与算法的文章就介绍到这了,更多相关Innodb索引与算法内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！
