mysql实战45讲

本文摘抄自 极客时间【MySQL实战45讲】

为什么要有索引？索引的作用是什么？

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。一本书我们可以通过目录中快速的定位其中的某一个知识点；对于数据库而言索引其实就是它的目录，可以通过索引快速的定位都某一条或多条记录。

常见索引模型

Hash表

哈希表是一个以 键-值（key-value） 存储数据的结构，我们只要输入待查找的值即 key，就可以找到对应的值即 value。

结构特点

把值放在数组里，用一个哈希函数把 key 转换成一个确定的位置，然后把 value 放在数组的这个位置。当多个 key 值经过哈希函数的换算会出现同一个值的情况。这时候会拉出一个链表进行存储。

案例

假设现在维护一个身份证信息和姓名的表，表示根据身份证查找对应的名字，这时对应的哈希索引示意图如下

图 1 哈希表示意图

图中，User2 和 User4 根据身份证号算出来的值都是 N，所以后边跟了一个链表存储。如果要找到 User2 对应的名字是什么，首先通过哈希函数计算出 IDcardn2 的值为 N，然后按顺序遍历找到 User2。

在这里四个 IDcardn 的值并不是递增的，这样做的好处就是增加的时候会很快，直接往后边追加；缺点是数据的存储并不是有序的，所以在做区间查询时会进行全表扫描，速度会非常慢。

哈希表这个结构只适用于等值查询。

有序数组

结构特点

将数据存放到数组中，数据在数组中是按顺序存储的，从左到右依次从大到小或从小到大。

案例

以哈希表中的例子，使用有序数组实现的结果如下

图 2 有序数组示意图

这里假设身份证是没有重复的，这个数组是按照身份证的递增顺序保存的。这时候如果刷要查询 IDcardn2 对应的姓名，用二分查找法可以快速定位到这条记录，同时如果要进行范围查询也是很快的，比如要查找身份证号在 [ID_card_X, ID_card_N] 区间的 User，可以先用二分查找法找到 ID_card_X 的值，如果没有则找到大于 ID_card_X 的第一个值，然后向右遍历，知道找到第一个大于 ID_card_N 的值退出循环。

但是往数组中插入一条记录的时候需要挪动后边所有的元素，这样的成本太高，同样的删除一条记录也会导致后边所有的元素往前挪动。

有序数组结构适用于等值和范围查询，但是插入和删除的效率太慢。

二叉搜索树

结构特点

二叉搜索树每个节点大于左儿子小于右儿子。

案例

上文例子，二叉搜索树实现如下

图 3 二叉搜索树示意图

如果我们要找到 IDcardn2 的话，根据二叉搜索树的特点，按照图中的搜索顺序依次是：UserAUserCUserFUser2。

InnoDB索引模型

InnoDB 使用了 B+ 树索引模型，数据都是存储在 B+ 树中的，每一个索引都对应一棵 B+ 树。

B-Tree

B树 是一棵多路平衡树且有以下特点：

m阶B树 表示该树每个节点最多有 m 个孩子； 除根节点和叶子节点外，其它每个节点至少有 ceil(m / 2) 个孩子； 若根节点不是叶子节点，则至少有两个孩子； 所有叶子节点都在同一层，叶子节点不包含任何关键字； 每个叶子节点包含 n 个关键字信息；Ki（i = 1...n） 为关键字，且关键字按顺序升序排序 k(i-1) Pi 为指向子树根的节点，且指针 P(i-1) 指向子树中所有节点的关键字均小于 Ki，但都大于 K(i-1)； 关键字个数 n 必须满足： ceil(m / 2) - 1