mysql索引
最近一直在看《高性能mysql》，关于索引部分，以前接触过，但是不是特别深入，仅仅了解过主键索引，本片博文用来加深对索引部分的印象，博主学习的《高性能mysql》是2013年5月版，主要是基于 mysql5.5
mysql索引分类
本文主要介绍以下两种索引
- B+Tree索引（书中写的是B-Tree，根据译者说明，应该是B+Tree）
- 哈希索引
B+Tree索引
既然原书中写的是 B-Tree，我们就简单介绍一下 B-Tree，介绍 B+Tree时也方便一点
B-Tree 是 B树而不是 B减树，中间的 - 是连接符
B-Tree 是一种多叉平衡查找树，对比二叉平衡查找树（又叫 avl树），B-Tree 每个节点的子节点数目可以大于两个，如果B-Tree树中每个节点的子节点数目最大为 m，则为m阶B-Tree，除此以外B-Tree与 avl树没有明显的不同
B+Tree 是在 B-Tree树上的一种拓展，百科上面对B+Tree讲述的比较细致，这里主要有三点需要额外的注意
- 除了最后的叶子节点，每个叶子节点都有指向下一个叶子节点的指针，从而所有叶子节点形成了一个有序的链表，连续顺序查找时会非常节省时间
- 每个非叶子节点不存储具体的数据（严格来说时指向数据的指针），而仅仅存储键
- 当索引的键不止一个时（譬如，使用 <last_name, first_name, date> 作为索引）时，只有在前一个键匹配的情况下才能去查找下一个。譬如，如果 last_name匹配，则可以去匹配 first_name，如果 first_name也已经匹配，则可以去匹配 date。如果不提供 last_name的值，则不能直接去匹配 first_name，也不能直接去匹配 date
B+Tree示意图如下
图片来自百度百科
我们可以模拟一下B+Tree索引的查找过程
譬如，我们需要查找 <last_name=Y,first_name=XC,date=2020.10.26,time=night>，首先我们需要建立这样的索引 key(last_name,first_name,date,time)，上图中的 key就变成数据库中这四个项的组合，然后
- 根据 last_name=Y 在对应的 B+Tree中查找
- 找到对应索引后，再根据 first_name查找
- 找到对应索引后，再根据 date=2020.10.26查找（如果这里 date是范围表示，譬如 date<2030.1.1，则time索引不会被查找）
- 最后按照 time索引查找
在查找到对应的叶子节点后，直接访问也叶子节点指向的数据行，查找过程结束。
我们回顾一下查找过程，主要的耗时在于索引树的遍历，假设我们使用的是 m 阶B+Tree，树的深度为 log(m)n，每一层查找平局耗时为 m/2，网上很多地方说这里可以用二分查找，但是博主仔细想了一下，第一，除非叶子节点，否则同一个父亲的子节点之间没有关联（只有叶子节点才用“串”起来）。第二，哪怕是叶子节点，他们之间的关联方式为指针连接，也很难通过下标的方式访问子节点
那么一次查找的平均耗时为 m/2*log(m)n，1/2为常数，可以省略，耗时可以写成 log(m^(1/m))n，对m^(1/m)求导可知，当 m=e的时候取最大值，此时耗时为最小值，由于这里m为整数，所以当 m=3时，有最好的效率，复杂度为 O(log(3)n)
如果我们不使用索引，直接查找数据行，复杂度为 O(n)
哈希索引
哈希索引使用哈希表实现，通过对不同的键值进行哈希计算，得到哈希码，通过访问哈希码能快速的访问到数据行
我们假设，使用 fname建立哈希索引，我们执行如下查询
SELECT lname FROM testhash WHERE fname='Peter';
通过哈希索引访问过程如下
- 计算 Peter的哈希值
- 使用哈希值查询到对应的记录指针
- 使用记录指针找到对应的数据行，并判断该行的 fname是否等于 Peter
由于底层使用了哈希表，所以查询速度非常快，不过哈希索引也存在着一定的问题
- 哈希索引不支持部分索引列匹配查找。
使用 B+Tree索引时，如果我们无法对整个查询字段进行索引查找，我们也可以根据前几项索引来优化我们的查找速度，但是哈希索引是建立时就将所有字段组合之后进行哈希，所以只提供部分字段值，我们无法生成对应的哈希值，也就无法使用哈希查找 - 哈希索引不支持范围查找。
由于字段经过哈希函数之后已经无法比较大小，所以范围查找是无法通过哈希索引的 - 如果哈希冲突很多，查找和维护的代价也会很高
综上，哈希索引在部分情况下效率极高，特别是当数据行的键重合度比较低，查询多是等值查询时。我们可以在通过做CRC32或者取用MD5的一部分作为我们的键，降低数据行的键重合度来优化我们的哈希索引。
网友评论