每日归档： 2017年6月3日

MySQL 深入理解索引

leokim / / MYSQL

深入理解索引

  1. 索引基础理论知识

  2. B+树索引

  3. 哈希索引

  4. 理解B+树，哈希索引结构及区别

  5. 理解常见索引的基本概念：主键索引，唯一索引，普通索引，联合索引之间的区别

  6. 理解MyISAM和InnoDB的索引结构区别

  7. 理解如何通过索引提高SQL效率

binary search， 二分查找法，也叫折半查找（折半搜索，二分查找算法，二分搜索），是一种再有序数组中查找某一特定元素的搜索算法。

这种搜索算法每一次比较都使搜索范围减小一般，可在最坏的情况下用0（log n）完成搜索任务。

二分查找法的优点是比较次数少，查找速度块，平均性能好

缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表

binary tree， 二叉树

每个节点至多只有两颗子树（不存在度大于2的节点），二叉树的子树有左右有序之分，次序不能颠倒

平衡二叉树

  1. 左右两个字数的高度差的绝对值不会大过1（<=1），且左右两个子树也是平衡二叉树

  2. 不平衡树会通过自旋，变成平衡树

  3. 平衡树和二叉查找的最大区别：前者是平衡的，后者未必

image.png

旋转后

image.png


image.png

image.png

image.png

用下面这些值来构造一个B树

ACGHEKQMFWLTZDPRXYS

1.构造一个4阶的B树，非根节点关键字数，小于2个就合并，大于4个就分裂

image.png

2.插入H

image.png

3.插入E,K,Q时不需要任何分裂操作,变成：

image.png

4.插入M之后就需要分裂了，M恰好时中间关键字元素，可以放在根节点

image.png

5.插入F,W,L,T不需要任何分裂操作

image.png

6.插入Z时，最右边的叶子节点空间满了，需要进行分裂操作，中间元素T上移到父节点中

image.png

7.插入D时，导致最左边的叶子节点被分裂，D是中间元素，上移到父节点

image.png

8.最后，当插入S时，第三个子节点需要分裂，但根节点已经满了，需要把根节点再次分裂，形成3层的B树

image.png

再来看下元素的删除

1.删除H，节点无需进行合并或分裂

image.png


2.删除T之后，最右边的子节点就没有父节点了，需要再找个新的元素放在其父节点

image.png


3.删除R

image.png

4.删除E之后，第一步变成了

image.png

可以把G,M,Q,X这4个元素提升到根节点，变成了

image.png

B+树是B树（B Tree）的变体，也是一种多路搜索树

  1. 非叶子节点的子树指针与关键字个数相同

  2. 为所有叶子节点增加一个链指针

  3. 所有关键字都在叶子节点出现

二叉树，B树，B+树的小结

Binary树：二叉树，每个节点之存储一个关键字，等于则命中，小于则走左节点，大于走右节点

B树：多路搜索树，没个节点存储M/2到M个关键字，非叶子节点存储指向关键字范围的子节点

所有关键字在整颗树中出现，且只出现一次，非叶子节点可以命中

B+树：在B-树基础上，为叶子节点增加链表指针，所有关键字都在叶子节点中出现，非叶子节点左右叶子节点的索引，B+树总是到叶子节点才命中



经典B+树结构

image.png

==========================================

B+树插入新元素时，可能会遇到3种情况

image.png

image.png

  1. 插入元素28（直接写入 叶子节点没有满）

  2. 插入元素70

    image.png

3.插入元素95

image.png

B+树删除元素时，也可能遇到3中情况

image.png

image.png

  1. 从这个B+树中删除元素70，变成了

image.png

2.再删除元素25，变成了：

image.png

3.再删除元素60，变成了：

image.png

用Innodb的时候一定要注意

  1. 要用顺序自增的主键

  2. 主键可以删除（也不建议）但是一定不要更新它，更新后可能会导致很多碎片产生，建议用字段表示，而不是直接删除，这样高并发下，新增数据性能以及删除数据性能都会比较高，避免频繁合并和分裂

哈希索引

在mysql中，只有memory存储引擎支持显示的哈希索引

关键字key，经过哈希算法hash（key）后，产生一个精确的结果值

image.png

如果有多个关键字相同 产生的hash值也是相同的 有多个重复相同key 会把值放在同一个链表里面，在扫描到这个key的时候就会把链表里的值全部都去取出来

哈希索引和B+树索引的区别：

  1. 先看下逻辑区别

    image.png

索引优点

1.加快数据检索效率

2.可以创建唯一性约束索引，保证数据库中每一行数据的唯一性

3.加速表和表连接效率

4.在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间


索引缺点

1.索引需要占用更多物理存储空间

2.当对表中的数据进行增加，删除和修改的时候，索引野要更新维护，降低了数据维护效率


哪些情况下建议创建索引

  1. 经常需要搜索的列

  2. 作为主键的列，有唯一约束索引

  3. 经常用在表连接的列

  4. 经常需要排序的列

  5. 经常使用再where字句中的列

  6. 经常需要排序/分组的列

哪些情况下不建议创建索引

很不经常被搜索的列

基数值很低的列

长text、blob类型列

对比参考ORACLE索引类型

对比一下MySQL的索引基本知识都有哪些

MySQL 聚集索引建议

PRIMARY KEY， 主键索引

唯一索引（约束）（unique key, UNIQUE Index Constraints）

联合索引 Combined Indexes，Multiple-Column Indexes

覆盖索引 covering indexes

最左索引/部分索引 （prefix indexex）

外键/约束（FIREUGN KEY Constraints）

MyISAM主键索引

InnoDB的主键索引和辅助索引

[MySQL FAQ]系列 — 为什么InnoDB表要建议用自增列做主键

[MySQL优化案例]系列 — InnoDB主键设计