一、索引

1、索引的定义

1.1 索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构,硬盘级存储方式

1.2 正确的创建合适的索引 是提升数据库查询性能的基础

2、索引如何实现的

索引是由插拔式的存储引擎来实现的,存储引擎可以定义在表结构中,一个库可以定义多个存储引擎。

如图:索引能够记录磁盘位置,根据对应关系,每个id有一个磁盘位置

微信图片_20190115140128.png

3、为什么要用索引

3.1 索引能极大的减少存储引擎需要扫描的数据量

3.2 索引可以把随机IO变成顺序IO 索引

3.3 可以帮助我们在进行分组、排序等操作时,避免使用临时表

4、为什么选择 B+tree 数据结构作为索引机制

在讲B + Tree之前先来看下其它几种二叉树运行机制

4.1 二叉查找树 Binary Search Tree

如图: 二叉树先进行根节点比较,再进行子节点比较。假如这是一幅id为索引的二叉树索引结构,比如我现在要查找id为7的位置,先从根节点10出发,发现7比10小,再比较左边的子节点5,发现7比5大,再比较5的右边子节点,此时刚好命中7,就定位到了要查找的数据位置。

微信图片_20190115141337.png

:父子节点的位置看插入的顺序和数值大小,比如第一个插入的就是根节点,小于上一个节点数值放在左边节点位置,大于等于上一个节点数值放在右边节点位置

问题:假设数据表主键id为唯一索引并且自增,那么此时二叉树根据ID的查找效率和全表扫描没有任何区别,会有很多IO的访问,如图

微信图片_20190115144049.png

总结:采用二叉树作为数据结构检索效率必须强依赖数据的分布,如果数据分布呈现一种线性链表的结构,那么效果就看不出来了,所以二叉树不适合作为mysql索引的索引机制。

4.2 平衡二叉查找树 Balanced Binary Search Tree

平衡二叉树 两种定义 有 相对平衡二叉树(平衡二叉树 某一个节点的高度差不会超过1) 和完全平衡二叉树AVL(整棵树的高度差不超过一个节点)

  1. AVL 完全平衡二叉树,依次插入8个数字呈现效果如图,为了保证数据的平衡,会变动数据的位置

image.png

  1. 相对平衡二叉树

一个节点就是一个磁盘块,一个磁盘块保存的数据是关键字和数据区,通过数据区加载数据,先比较根节点,加载到内存中,一般数据区放的是磁盘位置也可能放的是直接数据,p1和p2是指向子节点引用的指针地址,

总结:平衡二叉树虽然解决了出现线性链表的问题,但是树太高了,数据处的(高)深度决定着他的IO操作次数,IO操作耗时大,假设数据量较大此时的IO操作次数也会很多。每一个磁盘块(节点/页)保存的数据量太小了 没有很好的利用操作磁盘IO的数据交换特性, 也没有利用好磁盘IO的预读能力(空间局部性原理),从而带来频繁的IO操作,保存到数据量小同时也导致着空间的浪费。

4.3 多路平衡查找树 B-Tree

B-Tree 是一个绝对平衡树(即所有的子节点都在同一个高度)

多路表示的是不再和二叉树每个节点只有两条路,每个磁盘块存储这关键字和子节点引用指针,如下图的根节点,关键字为17、35,子节点引用指针为p1、p2、p3,关键字和路数的关系是: M条路数 M-1 个关键字

微信图片_20190115162527.png

检索过程:B-Tree为了保证绝对平衡关系,如果插入或者删除的数据不满足平衡关系,整个索引的数据结构会发生节点的左旋和右旋来维持整棵树的平衡,所以索引不能随意建立。

路数的确定:假设一个磁盘块大小为4k,该索引是一个int的主键索引,4byte的数据区加上 假定的子节点引用指针等所占用的大小4byte,那么此时的路数为:4k1024/8 = 512路,所以在建数据表的时候尽可能的减少列的数据长度,这样能够增加路数,减少IO操作,提高检索效率。(这里的磁盘大小不全是存储关键字和数据区,也会存储子节点的引用指针和部分冗余,考虑会考虑到磁盘IO操作局部性原理和磁盘预读。另外每个磁盘块的大小可以通过参数指定,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页,在许多操作系统中,页得大小通常为4k)

4.4 加强版多路平衡二叉树B+Tree

image.png

  1. B+节点关键字搜索采用闭合区间
  2. B+非叶节点不保存数据相关信息,只保存关键字和子节点的引用
  3. B+关键字对应的数据保存在叶子节点中
  4. B+叶子节点是顺序排列的,并且相邻节点具有顺序引用的关系
  5. B+树是B-树的变种(PLUS版)多路绝对平衡查找树、拥有B-树的优势
  6. B+树扫库、表能力更强
  7. B+树的磁盘读写能力更强 B+树的排序能力更强
  8. B+树的查询效率更加稳定(仁者见仁、智者见智)

二、Mysql 中B+Tree索引体现形式

1、Mysql中B+Tree索引体现形式-MyISAM

数据和索引分别存储,表定义文件 .frm,数据保存在MYD文件中,索引保存在MYI文件中,在MyISAM中索引数据结构B+Tree的叶子节点数据区存储的是MYD文件的磁盘位置的指针引用

2、Mysql中B+Tree索引体现形式-InnoDB

F3627B5A-6052-49a3-9032-8C8B455B8E21.png

除了表信息frm文件,只有ibd文件,索引结构文件和数据文件保存在一起。nnodb使用了聚集索引(clustered index)存储数据,如果一个主键被定义了,那么这个主键就是作为聚集索引,如果没有主键被定义,那么该表的第一个唯一非空索引被作为聚集索引,如果没有主键也没有合适的唯一索引,那么innodb内部会生成一个隐藏的主键作为聚集索引,这个隐藏的主键是一个6个字节的列,改列的值会随着数据的插入自增。

数据会保存在主键索引的叶子节点上, 其它的索引的都是辅助索引,然后再关联到主键索引

C2C98268-1365-403a-9E2B-A2ABAC94EF5E.png

聚集索引: 数据库表行中数据的物理顺序与键值的逻辑(索引) 顺序相同(因为索引和数据是保存在一起的),一个表只能有一个聚集索引,因为一个表的物理顺序只有一种情况,所以,对应的聚集索引只能有一个。

两种引擎的展现形式

三、索引机制的一些原则

1、列的离散型:count(distinct col) : count (col)

337059C5-5696-41ce-BFFE-24BB2DCCF6F7.png

越大离散型越好 结论: 离散性越高 选择性就越好,第一列name列离散型最好

选择性最好(离散性最好)原则

2、最左匹配原则

根据排序规则进行比较,比如ASCall码,从左往右一次比较,且不可跳过

9AD7E2C4-03B1-4096-B9B7-6FCA402D822F.png

3、联合索引介绍

  1. 单列索引,节点中关键字[name]
  2. 联合索引,节点中关键字[name,phoneNum] 如 张三+18379306930

单列索引是特殊的联合索引

4、联合索引列选择原则

  • 经常用的列优先 【最左匹配原则】
  • 选择性(离散度)高的列优先【离散度高原则】
  • 宽度小的列优先【最少空间原则】
  • 避免创建重复的冗余索引
  • 最小空间原则

5、覆盖索引

  • 如果查询列可通过索引节点中的关键字直接返回,则该索引称之为 覆盖索引
  • 覆盖索引可减少数据库IO,将随机IO变为顺序IO,可提高查询性能
  • 不需要索引到最后叶子节点,直接返回数据
  • 索引只有主键索引、唯一索引、普通索引,覆盖索引只是一种效果

6、索引总结

  • 索引列的数据长度能少则少
  • 索引一定不是越多越好,越全越好,一定是建合适的
  • 匹配列前缀可用到索引 like 9999%,like %9999%、like %9999用不到索引
  • Where 条件中 not in 和 <>操作无法使用索引; 匹配范围值,order by 也可用到索引
  • 多用指定列查询,只返回自己想到的数据列,少用select *
  • 联合索引中如果不是按照索引最左列开始查找,无法使用索引
  • 联合索引中精确匹配最左前列并范围匹配另外一列可以用到索引
  • 联合索引中如果查询中有某个列的范围查询,则其右边的所有列都无法使用索引;

推荐网址:

数据结构可视化 Data Structure Visualizations

MySQL索引背后的数据结构及算法原理及磁盘存取原理

BTree和B+Tree详解

58同城30条军规

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

越努力,越幸运!