Mysql基础——索引

内容

  • 索引基础知识点
  • 索引数据结构
  • 优化器为什么会选错索引?
  • 普通索引和唯一所有如何选择?
  • 如何给字符串添加索引?
  • 排序查询如何通过索引进行优化?
    • 通过联合索引来优化排序
    • order by工作原理是什么?

一 索引基础

  • 常见索引模型:哈希表、有序数组、搜索树
  • 哈希表:适合等值查询的场景
  • 有序数组:按顺序存储。查询用二分法就可以快速查询,时间复杂度是:O(log(N)),更新效率低
  • 有序数组的适用场景:静态存储引擎。
  • 主键索引和非主键索引
    主键索引的叶子节点存的是整行的数据(聚簇索引),非主键索引的叶子节点内容是主键的值(二级索引)主键索引只要搜索ID这个B+Tree即可拿到数据。普通索引先搜索索引拿到主键值,再到主键索引树搜索一次(回表);
  • 页分裂与页合并:当一个数据页满了,按照B+Tree算法,新增加一个数据页,叫做页分裂,会导致性能下降。空间利用率降低大概50%。当相邻的两个数据页利用率很低的时候会做数据页合并,合并的过程是分裂过程的逆过程。
  • 从存储和性能上看,自增主键是更好的选择,业务逻辑的字段做主键,则往往不容易保证有序插入,这样写数据成本相对较高,而且主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小;
  • 回表:根据二级索引找到数据,然后在回到主键索引树搜索的过程,称为回表
  • 覆盖索引:某索引已经覆盖了查询需求,称为覆盖索引,例如:select ID from T where k between 3 and 5,二级索引上已经有id值,不需要再次回表;
  • 最左前缀原则:B+Tree这种索引结构,可以利用索引的"最左前缀"来定位记录,只要满足最左前缀,就可以利用索引来加速检索。最左前缀可以是联合索引的最左N个字段,也可以是字符串索引的最左M个字符
    1. 第一原则是:如果通过调整顺序,可以少维护一个索引,那么这个顺序往往就是需要优先考虑采用的。
  • 索引下推:在MySQL5.6之前,只能从根据最左前缀查询到ID开始一个个回表。到主键索引上找出数据行,再对比字段值。MySQL5.6引入的索引下推优化,可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。

二 索引数据结构

mysql索引数据结构采用B+树,采用聚簇索引的方式来组织表,主键索引就是聚餐索引,树的B+树的叶子节点存储行的真实数据,非主键索引的叶子节点存储的是主键的值。

2.1 聚簇索引

每个InnoDB的表都拥有一个索引,称之为聚簇索引,此索引中存储着行记录,一般来说,聚簇索引是根据主键生成的。为了能够获得高性能的查询、插入和其他数据库操作,理解InnoDB聚簇索引是很有必要的。

聚簇索引按照如下规则创建:

  • 当定义了主键后,InnoDB会利用主键来生成其聚簇索引;
  • 如果没有主键,InnoDB会选择一个非空的唯一索引来创建聚簇索引;
  • 如果这也没有,InnoDB会隐式的创建一个自增的列来作为聚簇索引。

Note: 对于选择唯一索引的顺序是按照定义唯一索引的顺序,而非表中列的顺序, 同时选中的唯一索引字段会充当为主键,或者InnoDB隐式创建的自增列也可以看做主键。
聚簇索引整体是一个b+树,非叶子节点存放的是键值,叶子节点存放的是行数据,称之为数据页,这就决定了表中的数据也是聚簇索引中的一部分,数据页之间是通过一个双向链表来链接的,B+树是一棵平衡查找树,也就是聚簇索引的数据存储是有序的,但是这个是逻辑上的有序,但是在实际在数据的物理存储上是,因为数据页之间是通过双向链表来连接,假如物理存储是顺序的话,那维护聚簇索引的成本非常的高。

2.2 B+定义:

B+树满足如下条件,即可称之为m阶B+树:

  • 根结点只有一个,分支数量范围为[2,m]
  • 分支结点,每个结点包含分支数范围为[ceil(m/2), m];
  • 分支结点的关键字数量等于其子分支的数量减一,关键字的数量范围为[ceil(m/2)-1, m-1],关键字顺序递增;

三 优化器为什么会选错索引?

  • 选索引依据:优化器会根据扫描行数、是否使用临时表、是否排序等因素进行综合判断选择哪个索引;
  • 扫描行数:根据索引的“区分度”来估算扫描行数,一个索引上不同的值越多,这个索引的区分度就越好。而一个索引上不同的值的个数,我们称之为“基数”(cardinality)。也就是说,这个基数越大,索引的区分度越好。
    1.可以通过:show index from table来查看cardinality
  • 优化器选错索引时如何办?
    1.采用 force index 强行选择一个索引;
    2.可以考虑修改语句,引导 MySQL 使用我们期望的索引
    3.在有些场景下,我们可以新建一个更合适的索引,来提供给优化器做选择,或删掉误用的索引。
  • 索引统计信息不准确导致的问题,可以用 analyze table 来解决。

四 普通索引和唯一所有如何选择?

如果业务不需要唯一索引来控制数据的唯一性,那么尽量优先考虑普通索引,原因在于唯一索引用不上change buffer机制来改进性能,
2.1 change buffer
在实际过程中,mysql利用change buffer对要更新行的数据页不在内存这种情况做了优化,针对数据页不在内存这种情况,如果更新操作总是需要去随机IO磁盘拿取数据,效果会差一些,所以在buffer pool内存中开辟了一段空间change buffer,当有更新、delete、 insert语句时会把这个操作先写入change buffer, 之后在进行merge操作时,再把change buffer记录的操作应用到原数据页;

  • 更新操作时,如果语句中有普通索引,则对普通索引的插入操作会利用change buffer,主键索引则不会,因为数据库对唯一索引的操作总是要把数据页读入内存,进行是否重复的判断,既然已经读入内存了,则不需要change buffer再来优化了;

五 如何给字符串添加索引

  • 直接创建完整索引,这样可能比较占用空间;
  • 创建前缀索引,节省空间,但会增加查询扫描次数,并且不能使用覆盖索引;
  • 倒序存储,再创建前缀索引,用于绕过字符串本身前缀的区分度不够的问题;
    1.用于正序时,前缀重复率的,而字段倒叙后重复率的情景
  • 创建 hash 字段索引,查询性能稳定,有额外的存储和计算消耗,跟第三种方式一样,都不支持范围扫描。
    1.额外多建立一个索引字段存储csc32计算得到hash值,通过这个字段来索引数据

六 排序查询如何通过索引进行优化?

6.1 通过联合索引来优化排序

例如有个表:

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `city` varchar(16) NOT NULL,
  `name` varchar(16) NOT NULL,
  `age` int(11) NOT NULL,
  `addr` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `city` (`city`)
) ENGINE=InnoDB;

执行如下语句时:

select name, city, age from people where city='昆明' order by name limit 100;
  • 这样的查询,可以考虑添加联合索引(city,name)来加速排序,如果只在city上添加索引,那么name是无序的,mysql server会通过全字段排序或是rowid 排序算法来进行排序,效果都会大打折扣,而建立(city, name)联合索引,相同的city的所有行,就已经是排好序的,避免了排序;
  • 如果是高频查询,还可以考虑(city, name, age)的联合索引,避免了回表,再次提升速度;

6.2 order by 是如何工作的呢?

mysql排序执行方式有两种,分别是:全字段排序和rowid排序。
全字段排序:
例如上面的搜索语句,根据city获取数据,然后根据name排序,其基本流程是:

  • 初始化 sort_buffer,确定放入 name、city、age 这三个字段;
  • 从索引 city 找到第一个满足 city='昆明’条件的主键 id,到主键 id 索引取出整行,取 name、city、age 三个字段的值,存入 sort_buffer 中;
  • 从索引 city 取下一个记录的主键 id;
  • 重复步骤上面步骤 直到 city 的值不满足查询条件为止,对 sort_buffer 中的数据按照字段 name 做快速排序;
  • 按照排序结果取前 100 行返回给客户端。
    sort_buffer有参数sort_buffer_size确定,如果判断sort_buffer_size不够排序使用,会用磁盘的临时文件进行辅助排序,采取归并的方式进行排序;

rowid排序:

  • 初始化 sort_buffer,确定放入两个字段,即 name 和 id;
  • 从索引 city 找到第一个满足 city='昆明‘条件的主键 id,到主键 id 索引取出整行,取 name、id 这两个字段,存入 sort_buffer 中;
  • 从索引 city 取下一个记录的主键 id;
  • 重复上面步骤直到不满足 city='昆明’条件为止,对 sort_buffer 中的数据按照字段 name 进行排序;遍历排序结果,取前 1000 行,并按照 id 的值回到原表中取出 city、name 和 age 三个字段返回给客户端。
    并不是所有order by语句就一定要用到排序操作,只有当数据本身是无序时,才会进行排序操作,如果数据是有序组织的,那么就不需要进行排序了,例如上述所说的如果city和name字段建立的联合索引,那么数据是有序组织的,在查询时就不需要排序了,直接确实数据返回个客户端就好。

引用:《丁奇45讲》

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

推荐阅读更多精彩内容