江苏龙网

  1. 首页 > 人文 > >

产业气象站|都懂的索引绝技，MySQL性能优化做得好的人

一步一步推导出MySQL索引的底层数据结构 。
MySQL作为互联网中非常热门的数据库 ， 其底层的存储引擎和数据检索引擎的设计非常重要 ， 尤其是MySQL数据的存储形式以及索引的设计 ， 决定了MySQL整体的数据检索性能 。
我们知道 ， 索引的作用是做数据的快速检索 ， 而快速检索实现的本质是数据结构 。 通过不同数据结构的选择 ， 实现各种数据快速检索 。 在数据库中 ， 高效的查找算法是非常重要的 ， 因为数据库中存储了大量数据 ， 一个高效的索引能节省巨大的时间 。
比如下面这个数据表 ， 如果MySQL没有实现索引算法 ， 那么查找id=7这个数据 ， 那么只能采取暴力顺序遍历查找 ， 找到id=7这个数据需要比较7次 ， 如果这个表存储的是1000W个数据 ， 查找id=1000W这个数据那就要比较1000W次 ， 这种速度是不能接受的 。
产业气象站|都懂的索引绝技，MySQL性能优化做得好的人
文章图片
一、MySQL索引底层数据结构选型
1、哈希表（Hash）
哈希表是做数据快速检索的有效利器 。
哈希算法：也叫散列算法 ， 就是把任意值(key)通过哈希函数变换为固定长度的key地址 ， 通过这个地址进行具体数据的数据结构 。
产业气象站|都懂的索引绝技，MySQL性能优化做得好的人
文章图片
考虑这个数据库表user ， 表中一共有7个数据 ， 我们需要检索id=7的数据 ， SQL语法是：
select*fromuserwhereid=7
哈希算法首先计算存储id=7的数据的物理地址addr=hash(7)=4231 ， 而4231映射的物理地址是0x77 ， 0x77就是id=7存储的额数据的物理地址 ， 通过该独立地址可以找到对应user_name="g"这个数据 。 这就是哈希算法快速检索数据的计算过程 。
但是哈希算法有个数据碰撞的问题 ， 也就是哈希函数可能对不同的key会计算出同一个结果 ， 比如hash(7)可能跟hash(199)计算出来的结果一样 ， 也就是不同的key映射到同一个结果了 ， 这就是碰撞问题 。 解决碰撞问题的一个常见处理方式就是链地址法 ， 即用链表把碰撞的数据接连起来 。 计算哈希值之后 ， 还需要检查该哈希值是否存在碰撞数据链表 ， 有则一直遍历到链表尾 ， 直达找到真正的key对应的数据为止 。
产业气象站|都懂的索引绝技，MySQL性能优化做得好的人
文章图片
产业气象站|都懂的索引绝技，MySQL性能优化做得好的人
文章图片
从算法时间复杂度分析来看 ， 哈希算法时间复杂度为O（1） ， 检索速度非常快 。 比如查找id=7的数据 ， 哈希索引只需要计算一次就可以获取到对应的数据 ， 检索速度非常快 。 但是MySQL并没有采取哈希作为其底层算法 ， 这是为什么呢？
因为考虑到数据检索有一个常用手段就是范围查找 ， 比如以下这个SQL语句：
select*fromuserwhereid&gt3
针对以上这个语句 ， 我们希望做的是找出id&gt3的数据 ， 这是很典型的范围查找 。 如果使用哈希算法实现的索引 ， 范围查找怎么做呢？一个简单的思路就是一次把所有数据找出来加载到内存 ， 然后再在内存里筛选筛选目标范围内的数据 。 但是这个范围查找的方法也太笨重了 ， 没有一点效率而言 。
所以 ， 使用哈希算法实现的索引虽然可以做到快速检索数据 ， 但是没办法做数据高效范围查找 ， 因此哈希索引是不适合作为Mysql的底层索引的数据结构 。
2、二叉查找树(BST)
二叉查找树是一种支持数据快速查找的数据结构 ， 如下图所示:
产业气象站|都懂的索引绝技，MySQL性能优化做得好的人
文章图片
二叉查找树的时间复杂度是O(lgn) ， 比如针对上面这个二叉树结构 ， 我们需要计算比较3次就可以检索到id=7的数据 ， 相对于直接遍历查询省了一半的时间 ， 从检索效率上看来是能做到高速检索的 。 此外二叉树的结构能不能解决哈希索引不能提供的范围查找功能呢？


推荐阅读


上一篇：手机中国|12全系四款曝光：售价、内存有惊喜，iPhone

下一篇：快科技|Plus全球首发！这下100%无槽点了，6000mAh+865