去年准备的团队内部分享 ᕦ(￣.￣)ᕤ
哈希索引
查 找
哈希索引为每个索引字段计算哈希值，如上图中的 lisi、wangwu 的哈希值为 127，找到哈希值 127 对应的物理地址，地址指向链表，遍历链表上的所有行，找出所需数据
优 点
- 精确查找非常快，一次定位，如
=、<>和in
缺 点
- 不能排序
- 不能模糊查询和范围查询，如
LIKE、>、<、BETWEEN AND等 - 复合索引不能利用部分索引字段查询
- 不适合将重复值较多的列设置为索引
二叉查找树
定 义
- 没有键值相等的结点
- 若左子树非空，则左子树上所有结点的值均小于它父结点的值
- 若右子树非空，则右子树上所有结点的值均大于它父结点的值
- 左右子树也分别为二叉查找树
查 找
如查键值为 b 的结点：
- 根结点的值是
3，b > 3，接着找3的右子树 - 找到
a，b > a，接着找a的右子树 - 找到
c，b < c，接着找c的左子树，找到b
缺 点
容易偏向一侧，形成链表结构，导致查找效率降低
AVL 树（自平衡二叉查找树）
想提高查找性能，需要建立一棵结构更加合理的二叉树！
定 义
- 首先是一棵二叉查找树
- 带有平衡条件：每个结点的左右子树的高度之差的绝对值最多为
1
特 点
增减结点不需要完全重建树，通过一次或多次树旋转来达到平衡
缺 点
随着结点数量增加，树的高度也会越来越高，查找效率越来越低（同样适用于其它二叉树）
B 树
什么叫度？
结点的度：一个结点含有的子树个数
一棵树中，最大结点的度称为树的度，一棵度为 m 的 B 树称为 m 阶 B 树
定 义
对于一棵 m 阶 B 树：
- 根结点：
1 <= 关键字个数 <= m-1（度数 >= 2） - 中间结点（非根、非叶子结点）：
ceil(m/2)-1 <= 关键字个数 <= m-1（度数 = 关键字个数 + 1） - 所有的叶子结点都位于同一层
优 点
一个结点包含多个关键字，有效降低了树的高度
缺 点
范围查找性能不高
B+ 树
注意：网上对于
B+树的描述不太一致，这里是其中一种定义
定 义
对于一棵 m 阶 B+ 树：
- 根结点：
1 <= 关键字个数 <= m（度数 >= 2） - 中间结点：
ceil(m/2) <= 关键字个数 <= m（度数 = 关键字个数） - 有
n个子结点的结点必有n个关键字 - 所有叶子结点都位于同一层且构成一个有序链表
与 B 树的区别
- 中间结点包含关键字个数比
B树多1个，且每个元素不保存数据，只用来索引，所有数据都保存在叶子结点 - 所有的中间结点关键字都同时存在于子结点，在子结点中是最大（或最小）元素
优 点
- 查找必须到叶子结点（
B树只要找到匹配结点即可），B+树的查找性能更稳定 - 中间结点没有数据，同样大小的磁盘页可以容纳更多关键字，这就意味着，
B+树比B树更加的矮胖，相应会减小IO次数
MyISAM 引擎
先找到 B+ 树的叶子结点，再通过叶子结点指向数据记录的物理地址，这种方式称之为 非聚簇索引
InnoDB 引擎
与 MyISAM 引擎不同，InnoDB 是 聚簇索引，即数据文件本身就是索引文件，叶子结点包含了完整的数据记录
辅助索引的叶子结点也包含完整的数据记录吗？
当然不是！辅助索引的叶子结点存储的是主键索引的值，除非查询的字段都存在于辅助索引，否则都需要查找两次：
- 查找辅助索引获得主键的值
- 通过主键的值到主键索引获得对应的数据记录
关于 MySQL 优化
就像通过推导才能使数学公式不那么生涩难懂，了解了索引的数据结构，回头看那些关于 MySQL 优化的技巧，就能明白其中的原理~
1. 索引是不是建越多越好？
当然不是，索引占用大量的空间，维护索引有性能开销
2. 为什么尽量使用自增字段做主键索引？
- 自增主键有时在分页等场景下有用
- 非自增的主键可能在插入新记录时数据文件会频繁的调整
- 辅助索引叶子结点包含主键值，如果使用过长的字段会导致辅助索引体积变大
3. 为什么索引支持最左匹配原则？
一个索引不论是单字段还是多字段，只创建一棵树，复合索引就按多字段排序，假设复合索引有两个字段，值分别是：（a,1）、（b,2）、（b,1）、（a,2），则最终叶子节点排序为 （a,1）、（a,2）、（b,1）、（b,2），这也就是为什么索引支持 最左匹配原则，同理可得范围查询可以用到索引，但是后面的字段无法用到索引
4. LIMIT 0,100 与 LIMIT 1000000,100 性能一样吗？
不一样！LIMIT 1000000,100 性能更低，如果只用到主键索引，相差没那么大。如果用到辅助索引，通过辅助索引查出来的值需要再到主键索引里二次查找，直到丢弃1000000 行之后取 100 行，查询肯定要慢的多
5. 使用 LIKE 查询字符串前缀可以使用索引吗？
在 B+ 树上按顺序比较字符串大小，并判断下一步要查询左子树还是右子树，故 LIKE x% 可以使用索引，LIKE %x 不能使用索引