大数据&云计算MySQL性能优化做得好的人，都懂的索引绝技
一步一步推导出 MySQL索引的底层数据结构 。
MySQL作为互联网中非常热门的数据库 ， 其底层的存储引擎和数据检索引擎的设计非常重要 ， 尤其是 MySQL数据的存储形式以及索引的设计 ， 决定了 MySQL 整体的数据检索性能 。
我们知道 ， 索引的作用是做数据的快速检索 ， 而快速检索实现的本质是数据结构 。 通过不同数据结构的选择 ， 实现各种数据快速检索 。 在数据库中 ， 高效的查找算法是非常重要的 ， 因为数据库中存储了大量数据 ， 一个高效的索引能节省巨大的时间 。
比如下面这个数据表 ， 如果 MySQL 没有实现索引算法 ， 那么查找 id=7 这个数据 ， 那么只能采取暴力顺序遍历查找 ， 找到 id=7 这个数据需要比较 7 次 ， 如果这个表存储的是 1000W 个数据 ， 查找 id=1000W 这个数据那就要比较 1000W 次 ， 这种速度是不能接受的 。
本文插图
一、MySQL索引底层数据结构选型
1、哈希表（Hash）
哈希表是做数据快速检索的有效利器 。
哈希算法：也叫散列算法 ， 就是把任意值(key)通过哈希函数变换为固定长度的 key 地址 ， 通过这个地址进行具体数据的数据结构 。
本文插图
考虑这个数据库表 user ， 表中一共有 7 个数据 ， 我们需要检索 id=7 的数据 ， SQL 语法是：
select * from user where id=7
哈希算法首先计算存储 id=7 的数据的物理地址 addr=hash(7)=4231 ， 而 4231 映射的物理地址是 0x77 ， 0x77 就是 id=7 存储的额数据的物理地址 ， 通过该独立地址可以找到对应 user_name="g"这个数据 。 这就是哈希算法快速检索数据的计算过程 。
但是哈希算法有个数据碰撞的问题 ， 也就是哈希函数可能对不同的 key 会计算出同一个结果 ， 比如 hash(7)可能跟 hash(199)计算出来的结果一样 ， 也就是不同的 key 映射到同一个结果了 ， 这就是碰撞问题 。 解决碰撞问题的一个常见处理方式就是链地址法 ， 即用链表把碰撞的数据接连起来 。 计算哈希值之后 ， 还需要检查该哈希值是否存在碰撞数据链表 ， 有则一直遍历到链表尾 ， 直达找到真正的 key 对应的数据为止 。
本文插图
本文插图
从算法时间复杂度分析来看 ， 哈希算法时间复杂度为 O（1） ， 检索速度非常快 。 比如查找 id=7 的数据 ， 哈希索引只需要计算一次就可以获取到对应的数据 ， 检索速度非常快 。 但是 MySQL并没有采取哈希作为其底层算法 ， 这是为什么呢？
因为考虑到数据检索有一个常用手段就是范围查找 ， 比如以下这个 SQL 语句：
select * from user where id >3
针对以上这个语句 ， 我们希望做的是找出 id>3 的数据 ， 这是很典型的范围查找 。 如果使用哈希算法实现的索引 ， 范围查找怎么做呢？一个简单的思路就是一次把所有数据找出来加载到内存 ， 然后再在内存里筛选筛选目标范围内的数据 。 但是这个范围查找的方法也太笨重了 ， 没有一点效率而言 。
所以 ， 使用哈希算法实现的索引虽然可以做到快速检索数据 ， 但是没办法做数据高效范围查找 ， 因此哈希索引是不适合作为 Mysql 的底层索引的数据结构 。
2、二叉查找树(BST)
二叉查找树是一种支持数据快速查找的数据结构 ， 如下图所示:
推荐阅读
- 金十数据|中国7月制造业交亮眼成绩单！上半年美国对华投资增长6%，好消息
- 金十数据|苹果欲向印转移6条生产线，印度手机市场混战：三星份额紧追小米
- 餐厅|大数据显示：二季度餐厅服务员求职环比上升超150%，快递员收入第一
- 美剧去哪看|状元们最后都干什么？权势巨子数据显示，3300名状元，最后只是……
- "飒"英雄!20岁女兵征服40吨远火车 巾帼不让秀媚
- 零售店|194年历史！美国最古老奢侈品百货店Lord&Taylor申请破产保护
- 中国天气网|哪些台风与“黑格比”相似，大数据看8月台风
- 新闻科技快报 华云数据用创新技术夯实中国信创“云基座”
- 问董秘|因为公司的发动机产品满足国六标准...，投资者提问：在公司营销数据和半年报中发现
- 天擎|海纳百川 风云际会——气象大数据云平台“天擎”