MySQL 索引介绍

本文章讲解 Hash、二叉树、平衡二叉树、B-Tree、BTree 索引的逻辑情况查找都是索引操作当数据量较大时索引的大小可能有几个 G甚至更多为了减少索引在内存的占用数据库索引是存储在磁盘上的将索引以及索引对应的数据页从磁盘加载到内存中的过程是很花费时间的进行索引查询的时候不可能把整个索引全部加载到内存只能逐一加载站在 MySQL 的角度上磁盘的 I/O 操作次数对索引的使用效率至关重要如果索引的数据结构尽量减少硬盘的 I/O 操作对应消耗的时间也就越小常见的加速查找的数据结构有两类树如平衡二叉搜索树查询/插入/修改/删除的平均时间复杂度都是 O(log2N)哈希如HashMap查询/插入/修改/删除的平均时间复杂度都是 O(1)Hash 索引Hash 本身是一个函数被称为散列函数。Hash 算法是通过某种确定性的算法如MD5、SHA1 等将输入转变为输出。相同的输入永远可以得到相同的输出假设输入内容有微小偏差在输出时通常会有不同的结果举例要验证两个文件是否相同时不需要把两份文件直接拿来比对只需用 Hash 函数对两份文件进行计算最后比较这两个 Hash 函数的结果是否相同即可知道这两个文件是否相同采用 Hash 进行检索效率非常高基本上一次检索就可以找到数据而 B树需要自上向下依次查找多次访问节点才能找到数据中间需要多次 I/O 操作从效率来说 Hash 比 B树更快但索引结构并没有设计成 Hash 型原因如下Hash 索引只支持等值、、IN 查询不支持范围查询Hash 索引存储数据时没有顺序的在 ORDER BY 的情况下 Hash 索引还需要对数据重新排序对于联合索引的情况Hash 值是将联合索引键合并后一起来计算的无法对单独的一个键或者几个索引键进行查询对于等值查询来说Hash 索引的效率更高但如果索引列的重复值很多效率就会降低因为遇到 Hash 冲突时需要遍历指针来进行比较找到查询的关键字是非常耗时的所以 Hash 索引通常不会用到重复值多的列上InnoDB 本身不支持 Hash 索引但是提供自适应 Hash 索引如果某个数据被频繁查询就会将这个数据页的地址存放到 Hash 表中下次查询的时候就可以直接找到这个页面的所在位置这样让 B树也具备了 Hash 索引的优点show variables like%adaptive_hash_index;# 查看是否开启自适应 Hash# ON已启用自适应哈希索引功能默认值# OFF已关闭自适应哈希索引功能二叉搜索树如果利用二叉树作为索引结构那么磁盘的 IO 次数和索引树的高度是相关的二叉搜索树的特点1.1. 一个节点只能有两个子节点也就是一个节点度不能超过21.2. 左子节点 本节点 右子节点比我大的向右比我小的向左查找规则搜索某个节点和插入节点的规则一样假设搜索插入的数值为 key2.1. 如果 key 大于根节点则在右子树中进行查找2.2. 如果 key 小于根节点则在左子树中进行查找2.3. 如果 key 等于根节点也就是找到了这个节点返回根节点即可2.4. 查找方式如下如果二叉树的深度非常大则需要多次比较才能找到节点如下图所示为了提高查询效率需要减少磁盘 IO 次数尽量降低树的高度把原来瘦高的树结构变的矮胖树的每层的分叉越多越好平衡二叉树平衡二又树又称为 AVL 树。它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树在二叉搜索树的基础上增加了约束常见的平衡二叉树有很多种包括了平衡二叉搜索树、红黑树、数堆、伸展树。而平衡二叉树是最早提出来的自平衡二叉搜索树一般提到的平衡二叉树指的就是平衡二叉搜索树数据查询的时间主要依赖于磁盘 I/O 的次数如果采用二叉树的形式即使通过平衡二叉搜索树进行了改进树的深度也是 O(log2n)当 n 比较大时深度也是比较高的比如下图的情况每访问一次节点就需要进行一次磁盘 I/O 操作对于上面的树来说需要进行5次 I/O 操作,虽然平衡二叉树的效率高但是树的深度也同样高这就意味着磁盘 I/O 操作次数多会影响整体数据查询的效率缺点一个节点最多分裂出两个字节点树的高度太高导致IO次数过多节点中只保存了一个关键字保存的内容太少如果把二叉树改成 M 3 时同样的3个节点可以由三叉树来进行存储B-TreeB 树简写为 B-Tree横杠表示这两个单词连起来的意思即多路平衡查找树。它的高度远小于平衡二叉树的高度。结构如下图所示假设要查找的关键字是9步骤如下与根节点的关键字 (1735) 进行比较9小于17得到指针 P1按照指针 P1 找到磁盘块2关键字为 (812)因为9在8和12之间得到指针 P2按照指针 P2 找到磁盘块6关键字为 (910)找到了关键字9如果查找的是 17直接在根节点就可以查到结果优点B 树的节点既存储索引也存储数据如果将频繁访问的数据放到根节点附近就会大大的提高热数据查询的效率缺点B 树中每个节点既存储索引也存储数据当数据比较大时候会导致每个节点存储的 key 变少了就会导致 B 树的层数变高增加 IO 次数BTreeMySQL 默认使用 Btree 索引是基于 B-Tree 做出的改进B树和 B 树的差异在于以下几点● 有 k 个孩子节点就有 k 个关键字即孩子数量 关键字数而 B 树中孩子数量 关键字数 1● 非叶子节点的关键字也会同时存在在子节点中并且是在子节点中所有关键字的最大或最小● 非叶子节点仅用于索引不保存数据记录和记录有关的信息都放在叶子节点中而 B 树中的非叶子节点既可以保存索引也可以保存数据记录● 所有关键字都在叶子节点出现叶子节点构成一个有序的双向链表如图所示B 树和 B树的区别B树的中间节点并不直接存储数据因为 B树每次只有访问到叶子节点才能找到对应的数据而 B树中非叶子节点也会存储数据会造成查询效率不稳定的情况有时访问到非叶子节点就可以找到关键字有时需要访问到叶子节点才能找到关键字缺少系统性。而且在 B树的角度上看非叶子节点完全可以存储更多数据页的目录项记录这样可以关联到更多的用户记录其次B树的查询效率更高因为通常 B树比 B 树更矮胖阶数更大深度更低查询所需要的磁盘 I/O 也会更少同样的磁盘页大小B树可以存储更多的节点关键字在查询范围上B树的效率也比 B 树高。因为所有关键字都出现在 B树的叶子节点中叶子节点之间会有指针数据又是递增的使得范围查找可以通过指针连接查找而 B 树则需要遍历才能完成范围的查找效率要低很多B 树和 B树都可以作为索引的数据结构在 MySQL 中采用的是 B树但 B 树和 B树各有自己的应用场景不能说 B树完全比 B 树好思考为了减少 I/O索引树是否会一次性加载数据库索引是存储在磁盘上的如果数据量很大必然导致索引的大小也会很大可能会有好几个 G当使用索引查询时候是不可能将全部几个 G 的索引都加载进内存的只能是逐一加载每一个磁盘页因为磁盘页对应着索引树的节点B树的存储能力如何为何说一般查找行记录最多只需1~3次磁盘 I/OInnoDB 存储引擎中页的大小为 16KB一般表的主键类型为 INT占用4个字节或 BIGINT占用8个字节指针类型也一般为4或8个字节也就是说一个页BTree 中的一个节点中大概存储 16KB / (8B8B) 16384B / 16B 1024 个键值假设这里的 K 取值为10^3也就是说一个深度为3的 B树索引可以维护 10^3 * 10^3 * 10^3 10 亿条记录假设一个数据页也存储10^3条行记录数据实际情况中每个节点可能不能填充满因此在数据库中BTree 的高度一般都在2~4层MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的也就是说查找某一键值的行记录时最多只需要1~3次磁盘 I/O 操作小结使用索引可以从海量的数据中快速定位想要查找的数据不过索引也存在一些不足比如占用存储空间、降低数据库写操作的性能等如果有多个索引还会增加索引选择的时间。使用索引时需要平衡索引的利提升查询效率和弊维护索引所需的代价在实际工作中还需要基于需求和数据本身的分布情况来确定是否使用索引尽管索引不是万能的但数据量大的时候不使用索引是不可想象的毕竟索引的本质就是提升数据检索的效率