MySQL调优笔记（二）深入理解 Mysql 索引底层原理
站长
· 阅读数 34
索引数据结构详解
Hash
- 使用哈希算法；
- 数组+链表；
哈希碰撞问题；
优点
从算法时间复杂度分析来看，哈希算法时间复杂度为 O（1），检索速度非常快。比如查找 id=1 的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快。
缺点
- 如果使用哈希算法实现的索引，SQL的范围查找怎么做呢？一个简单的思路就是一次把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。所以，使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效范围查找，因此哈希索引是不适合作为 Mysql 的底层索引的数据结构。
二叉树
- 如果insert的数据从小到大排序，该极端情况下会退化为线性链表，二分查找也会退化为遍历查找，时间复杂退化为 O（N），检索性能急剧下降。
红黑树&&平衡二叉树
- 红黑树：存在右倾趋势，树的高度只是没有线性链表那么夸张；
- 平衡二叉树：AVL 树是个绝对平衡的二叉树，因此它在调整二叉树的形态上消耗的性能会更多。每个树节点只存储了一个数据，每次查询都要进行多次磁盘IO。
- 可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。
B树
- 优秀检索速度，时间复杂度：B 树的查找性能等于 O（h*logn），其中 h 为树高，n 为每个节点关键词的个数；
- 每个节点存储多个数据，尽可能少的磁盘 IO，加快了检索速度；
- 可以支持范围查找。
B+树
- B树和B+树的区别：
- B树节点存储的是数据，B+树节点存储的是索引，只有叶子结点存在数据。单个节点也可以存储大量索引，使得树的高度降低，较少磁盘IO。（//TODO 回表操作）
- 且叶子结点通过链表连接起来，链表是有序的，在数据的范围查找场景中更高效。
B+树如何实现索引快速查找(//TODO)
索引的分类
聚集索引
- 索引项的排序方式和表中数据记录排序方式一致的索引；
非聚集索引
- 索引项顺序与物理存储顺序不同；
聚簇索引
- InnoDB存储引擎；
- 数据和索引都存储在同一个文件里。比非聚簇索引快，因为聚簇索引多一次磁盘IO。
非聚簇索引
- Myisam存储引擎；
- 一种数据存储方式；表数据和索引是分成两部分存储的，主键索引和二级索引存储上没有任何区别。使用的是B+树作为索引的存储结构，所有的节点都是索引，叶子节点存储的是索引+索引对应的记录的数据。
InnoDB和Myisam的区别
- InnoDB 节约磁盘空间；如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得非常巨大。
- Myisam 直接找到物理地址后就可以直接定位到数据记录，但是 InnoDB 查询到叶子节点后，还需要再查询一次主键索引树，才可以定位到具体数据。
为什么推荐使用自增主键做索引
- 如果主键为自增 id 的话，MySQL 在写满一个数据页的时候，直接申请另一个新数据页接着写就可以了。
- 如果主键是非自增 id，为了确保索引有序，MySQL 就需要将每次插入的数据都放到合适的位置上。
- 方便范围查找//TODO（因为索引是有序）
联合索引的底层数据结构
Mysql最左前缀优化原则
- 最左前缀匹配原则和联合索引的索引构建方式及存储结构是有关系的。
- 首先我们创建的index_bcd(b,c,d)索引，相当于创建了(b)、（b、c）（b、c、d）三个索引，看完下面你就知道为什么相当于创建了三个索引。
联合索引是首先使用多列索引的第一列构建的索引树，用上面idx_t1_bcd(b,c,d)的例子就是优先使用b列构建，当b列值相等时再以c列排序，若c列的值也相等则以d列排序。
select * from T1 where b = 12 and c = 14 and d = 3;-- 全值索引匹配 三列都用到。 select * from T1 where b = 12 and c = 14 and e = 'xml';-- 应用到两列索引。 select * from T1 where b = 12 and e = 'xml';-- 应用到一列索引。 select * from T1 where b = 12 and c >= 14 and e = 'xml';-- 应用到bc两列列索引及索引条件下推优化。 select * from T1 where b = 12 and d = 3;-- 应用到一列索引 因为不能跨列使用索引 没有c列 连不上。 select * from T1 where c = 14 and d = 3;-- 无法应用索引，违背最左匹配原则。