3.MySQL索引原理与使用原则

本章要点

1.索引原理
2.索引类型
3.使用原则
4.有关索引的几个概念

1. 索引原理

索引的出现其实就是为了提高数据查询的效率,就像书的目录一样;是一种排好序的数据结构。
本质就是:通过不断地缩小想要获取数据的范围来筛选出结果,同时把随机的事件变成顺序的事件。

1.1 索引的常见模型

常见的索引模型数据结构:哈希表、有序数组和搜索树。

  • 哈希表:一种以键 - 值(key-value)存储数据的结构(Map),只要输入待查找的键即 key,就可以找到其对应的值即 Value。哈希的思路很简单,把值放在数组里,用一个哈希函数把 key 换算成一个确定的位置,然后把 value 放在数组的这个位置。不可避免地,多个 key 值经过哈希函数的换算,会出现同一个值的情况。处理这种情况的一种方法是,拉出一个链表。链表过长时,性能交叉,且不支持范围查询。

哈希表这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些 NoSQL 引擎

  • 有序数组:有在等值查询和范围查询场景中的性能就都非常优秀。利用二分查找算法进行查找效率很快(O(log(N)))。但是,在需要更新数据的时候就麻烦了,往中间插入一个记录就必须得挪动后面所有的记录,成本太高。

有序数组索引只适用于静态存储引擎

  • 搜索树:他的特点是:父节点左子树所有结点的值小于父节点的值,右子树所有结点的值大于父节点的值,树可以是二叉树也可以是多叉树。

  • 使用搜索树其实能够保证数据按照键的顺序进行存储,也就是相邻的所有数据其实都是按照自然顺序排列的;

  • B 树和 B+ 树在数据结构上其实有一些类似,它们都可以按照某些顺序对索引中的内容进行遍历,对于排序和范围查询等操作,B 树和 B+ 树相比于哈希会带来更好的性能

  • B 树和 B+ 树相比,哈希作为底层的数据结构的表能够以 O(1) 的速度处理单个数据行的增删改查,但是面对范围查询或者排序时就会导致全表扫描的结果,而 B 树和 B+ 树虽然在单数据行的增删查改上需要 O(log n) 的时间,但是它会将索引列相近的数据按顺序存储,所以能够避免全表扫描。

总结:

使用B+树而不是二叉树的原因
  • 二叉树单边插入可能会退化成链结构
  • 大数据量下高度不可空
使用B+树而不是B树的原因
  • B+树节点大小更小,一次IO读入的节点数更多
  • B树数据存在各个节点中,而B+树的数据都在叶子节点中,遍历和区间访问性能大幅提高
  • B+树查询效率更加稳定
使用B+树而不是平衡二叉树或红黑树的原因
  • 在数据量比较大的情况下,平衡二叉树或红黑树高度不可控,而B+树的树高比平衡二叉树或红黑树低,IO次数少

所以MySQL选择了B+Tree

对于InnoDB的哈希索引,确切的应该这么说:

  • (1)InnoDB用户无法手动创建哈希索引,这一层上说,InnoDB确实不支持哈希索引;
  • (2)InnoDB会自调优(self-tuning),如果判定建立自适应哈希索引(Adaptive Hash Index, AHI),能够提升查询效率,InnoDB自己会建立相关哈希索引,这一层上说,InnoDB又是支持哈希索引的;

2. 索引类型

索引分类

  • 普通索引index :加速查找
  • 唯一索引
    主键索引:primary key :加速查找+约束(不为空且唯一)
    唯一索引:unique:加速查找+约束 (唯一)
  • 联合索引
    -primary key(id,name):联合主键索引
    -unique(id,name):联合唯一索引
    -index(id,name):联合普通索引
  • 全文索引fulltext :用于搜索很长一篇文章的时候,效果最好。

3. 使用原则

3.1 创建原则
  • 对于经常查询的字段,且区分度大的字段,建议创建索引。
  • 索引不是越多越好,一个表如果有大量索引,不仅占用磁盘空间,而且当表里数据有所更改,维护索引成本较大,且影响增、删、改的效率
  • 避免对经常更新的表进行过多的索引,因为当表中数据更改的同时,索引也会进行调整和更新,十分消耗系统资源。
  • 数据量小的表不需要创建索引,数据量小时索引不仅起不到明显的优化效果,对于索引结构的维护反而消耗系统资源。
  • 不要在区分度低的字段建立索引。比如布尔字段,只有 “失效” 和 “有效” ,建索引完全起不到优化效果。
  • 在频繁进行跑排列分组(即进行 group by 或 order by操作)的列上建立索引,如果待排序有多个,可以在这些列上建立组合索引

区分度公式:
count(distinct(column_name)) / count(*) -- 列的全部不同值个数/所有数据行行

3.2 联合索引的最左匹配原则

当B+Tree的数据项是复合的数据结构,比如(name,age,sex)的时候。

  • B+Tree是按照从左到右的顺序来建立搜索树的,比如当(张三,20,F)这样的数据来检索的时候,+Tree会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;

  • 但当(20,F)这样的没有name的数据来的时候,b+树就不知道下一步该查哪个节点,因为建立搜索树的时候name就是第一个比较因子,必须要先根据name来搜索才能知道下一步去哪里查询。

  • 比如当(张三,F)这样的数据来检索时,b+树可以用name来指定搜索方向,但下一个字段age的缺失,所以只能把名字等于张三的数据都找到,然后再匹配性别是F的数据了, 这个是非常重要的性质,即索引的最左匹配特性。

4.有关索引的几个概念

  • 回表: 如果语句是 select * from T where k=5(k含有索引字段),即普通索引查询方式,则需要先搜索 k 索引树,得到 ID 的值为 500,再到 ID 索引树搜索一次。这个过程回表

  • 覆盖索引:如果语句是 select k from T where k=5(k含有索引字段),即普通索引查询方式,则需要先搜索 k 索引树,这个称为覆盖索引(执行计划extra 字段为 Using index)。

  • 索引合并:对多个索引分别进行条件扫描,然后将它们各自的结果进行合并(intersect/union),当时and 关系的时候进行intersect操作,or关系的时候进行union操作。5.1版本以后才有的索引合并

  • 索引下推:索引下推(index condition pushdown )简称ICP,是指当进行查询的时候,可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数(执行计划extra 字段为 Using index condition)。5.6版本以后才有的索引下推

以联合索引(name, age)为例。如果现在有一个需求:检索出表中“名字第一个字是张,而且年龄是 10 岁的所有男孩”。

select * from tuser where name like '张%' and age=10 and ismale=1;

5.6版本以前,只是进行匹配查询:


image.png

5.6版本以后,索引下推:


image.png
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,552评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,666评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,519评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,180评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,205评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,344评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,781评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,449评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,635评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,467评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,515评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,217评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,775评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,851评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,084评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,637评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,204评论 2 341

推荐阅读更多精彩内容