图片

01

为啥BAT大厂,在数据库上都喜欢深入的问索引呢?

一线大厂,是很多人梦寐以求的盛典天堂。因为存在的无限的可能,可以帮你实现自己的远大抱负。大平台机会、视野、格局往往都比小厂多很多。但随之而来也是那高挑的技术门槛需等你迈过。好事物大家都喜欢,但毕竟僧多粥少。外加任务有难度,如果你没过硬的本领,那很难踏入平台,领会一览众山小的风采。不知你心里有没有小九九?


大厂产品大多数都成型很久,数据库里面存储的数据都以海量计算,如何在这种规模下的数据中做到快速筛选呢?那就需要你来答。

大家思路肯定和我一样,话不多说,加索引再说!索引为的就是提高数据的检索效率,进而减少请求的响应时间。

这时,有内涵的人可能会反问你啦?

那你说说索引有哪些类型?索引底层实现是什么结构?B+Tree的优点?聚簇索引和非聚簇的区别?索引一次读读取多少数据合适?为什么说索引会降低插入、删除、修改等维护任务的速度?

这一套组合拳,可能虐的你是体无完肤。让人招教不住,心理一万个xxx省略。送他一个微笑,然后再尴尬而不失优雅的离去。

图片

大家可能都知道查询慢了加索引,那为啥加?在哪些字段上加?以及索引的数据结构特点。索引优化、优点啥的都比较模糊或者不知道。

今天将是对索引来一次灵魂的拷问,在进一步对索引优化、常见大厂面试问题、SQL优化等内容进行分享。这是个大工程,大家得关注再看。深,那就得深出高度。MOG!太深啦

02

用索引,那你得知道索引是什么?

百度百科定义:索引是数据表中一列或多列的值进行排序的一种数据结构

故此,索引本质就是数据结构。这也是为什么每次数据表建立索引都需要设置在列字段上的原因。那常见数据结构有哪些?

常见数据结构大致可分为三大类,如下所示

  • 线性表:顺序表、链表、栈和队列;
  • 树结构:二叉树,堆、线索二叉树、红黑树、B-Tree等;
  • 图存储结构

但在数据库中常用数据结构为B+Tree、Hash索引

对于此,有人可能觉得有了Hash和那么多树结构(红黑树、B树、完全平衡二叉(AVL)树、B+树),为啥Mysql唯独喜欢B+树?

请听如下分解:

首先上场的是顽固不变Hash索引,这Hash索引又是什么?

哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才能生效额。切记!切记!切记!

哈希的思路很简单,以键-值( key-value )存储数据的结构,对于待查找每一行的数据值,用一个哈希函数把数据值换算成一个确定的位置即 key,位置就是哈希码,并且不同键值的行计算出来的哈希码也不一样。然后在 value 上存放每个数据行的指针。

图片

对这样的索引结构,执行如下sql语句的过程是什么呢?

  • 1
    select * from nezha where name='lianhua'

    MySQL首先计算’lianhua’的哈希值,并使用该值寻找对应的记录指针。然后根据指针寻找对应的数据,最后一步是比较读取的值是否为’lianhua’, 从而来确保就是要查找的行。

那如果改变为范围性查找就会存在问题。还记得上面的切记吗?因为它不支持范围匹配,只支持等值匹配。例如:

  • 1
    select * from nezha where name like '%lianhua'

    那像Hash这种等值查询还有哪些场景?

Hash故名思议体现的就是(key-value)结构。所以像 Redis、Memcached 及其他一些 NoSQL 引擎(如 Memory)。

那有没有既能快速查找,又可以支持范围型查找呢?

自然有,有序数组在等值查询和范围查询场景中的性能就都非常OK,足以满足你的口味。

图片

那它就好的没天理啦?不,世上没得十全十美的!

有序数组索引只适用于静态存储引擎,因为数组的空间必须是连续的,这就造成数组在内存中分配空间时必须找到一块连续的内存空间。所以新增、删除、修改数据时就会改变它的结构。

一下掉入无底洞,这在业务场景上怎样使用?

静态数据简单点可以理解为不会在变化的数据,那你就可以用于历史归档性的业务。比如你去年酷狗歌单、每上月的支付记录等,这类不会再修改的数据。

接下来上场的是层次不齐的树结构

树结构基础就是普通二叉树,其它树结构都是基于它演进产生。二叉树会根据元素值的大小来创建树形结构。所以它是有序的,并支持范围查找。具体可查看数据结构相关书籍。

但普通二叉树,有个问题,就是当元素是递增或递减时,它就会退化为线性表。

图片

为了解决这个问题,就出现了我们的完全平衡二叉树。可为何数据库没选择它呢

数据库操作都是在内存里面完成的,但最终还是要落地到磁盘。如果数据多了,树会变得很高。然而查询数据时,那都是从磁盘里面把数据读取出来放入到内存中。这样I/O操作成本就会随着树的高度而增加。这也是常说完全平衡二叉树具有高瘦特点。

好像女孩子都喜欢这样的吧!

图片

一般为节约成本,很多公司服务器采用的还是机械硬盘,这样一次千万级别的查询差不多就要10秒,这还不算网络传输、业务处理、CPU的执行时间,一但汇总那谁顶得住?

那这怎么解决呢?不可能一直让让它变高吧! 可使用B-Tree。

B-Tree的特征就是矮胖,也称为多叉树,就是在树的同一高度上开辟多个分叉来容纳元素。从而树在横向上面变宽了。这样减少了磁盘I/O的查询查找次数,从而提升了效率。

B-Tree的特点简写:

  • 每个节点中的元素(关键字)从小到大排列。
  • 每个节点都保存有数据

图片

那为什么最终数据库选择了B+Tree,而不是B-Tree呢?

B+Tree自然保持了B-Tree的矮胖特征,但它还做了升级的处理。就是让叶子节点保存数据,而非叶子节点保存关键字即可,并且会有指针指向下一个叶子节点。这样的好处是为了提高范围查找的效率。找到数据后直接根据指针向后读取即可,而B-Tree就不行,当它读取下一个数据,还需要再一次的进行索引树的查找。

img

B+Tree特点:

  • 所有的非叶子节点只存储关键字信息
  • 只有叶子节点存储数据
  • 所有叶子节点之间都有一个链指针

小结:最终MySQL选用B+Tree作为索引,从而提高检索索引时的磁盘IO效率,并且提高范围查询的效率,整个B+树里的元素也是有序的。因为B+Tree默认就是按照主键索引来构建的树结构。那你说呢?

03

索引是怎么构建的?

开发过程中,MySQL都首先B+Tree。在MySQL下还拥有Hash索引,也就是它拥有2大索引类型。具体选择用什么,可在创建表时进行选择。

img

那这索引到底是怎么创建出来的?

那还得分情况而定,分为以下2种

建表建索引

创建表的时候,先把索引字段建立好。如:

1
create table nezha(id int unsigned   AUTO_INCREMENT PRIMARY KEY, phone int not null,name varchar(16),index (phone))engine=InnoDB;

当添加数据时,数据库就会自动先去创建好索引结构,然后创建数据。最终在落地到磁盘上。

先建表,后添索引

这种情况需要注意,因为先建表,那可能你数据表已经拥有了大量数据,这时候你在添加索引,那你的整个数据库肯定会阻塞,因为数据库需要根据表中数据建立索引,这都是由数据库后台线程来完成。

这也是为什么线上数据库不要轻易变动索引,需根据用户低峰时间来操作。所以索引创建过多,那也算是需要耗费资源的。

一般还需要维护表和索引,你这里有什么建议吗?不妨留言说说你的提议,优化就留到下次。

所以当你的大表需要导入到其它数据库时,需在新数据库上先关闭索引,然后再添上索引,要不然效率就太低了。

04

索引的表现类型代表作有哪些?

乖乖,索引还有表现种类,这神马情况?

大家都知道B+Tree、Hash索引,但这些都底层实现的数据结构,而表现种类在明面上,我们常说的,例如:聚簇索引、非聚簇索引等,都包含了对应的数据结构。

问最多算聚簇索引、非聚簇索引,那它们是什么呢?

聚簇索引:索引和数据都存储在一起,代表作Innodb

非聚簇索引:索引和数据分开存储,代表\作*MyIASM*

上述的特性,也和它们的物理存储文件有关系。文件放在数据库安装目录下的data目录中

  • 1
    /mysql-57/data/mysql

    MyISAM结构如下:

.frm为表结构文件,存储像create alter等语句 .MYD为存储数据文件 .MYI为存储索引文件

图片

InnoDb结构如下:

.frm为表结构文件,.ibd为数据+索引文件

图片

在InnoDB存储引擎中,就一定都是聚簇索引吗?

并不是,只有主键索引被称为聚簇索引( clusteredindex )。除开主键以外的字段上创建的索引被称为非主键索引,非主键索引也被称为二级索引( secondary index )。

注:现在你该知道,为啥面试都不问你什么唯一、普通、联合索引了吧,那都是属于二级索引呢

那这两者之间有什么区别吗?区别在非主键索引的叶子节点内容是主键,当找到主键后,还需要根据主键再一次的进行索引树的查找,这个过程称之为回表。

例如:

如果语句是 select * from nezha where ID=7 ,即主键查询方式,那它只需搜索 ID 这棵 B+ 树;

如果语句是 select * from nezha where name = ‘哪吒’ ,即普通索引查询方式,则需要先搜索 name 索引树,得到 ID的值为 7,再到 ID 索引树搜索一次。这就是所谓的回表

图片

那这个问题怎么解决呀!

内心独白:哎呀!咋这么多问题,烦不烦。

这个好办,刚才我们是 select * ,查询所有记录,如果查询字段上只出现主键索引与创建索引的字段,那就不需要回表了。因为走二级索引时,就已经包含了你需要的字段列啦,那就不需要在回表了。这就被称之为索引覆盖,即索引已经包含了查询操作的值。

这也是为什么,当有多个字段需创建索引时,会创建联合索引,也是为了更好支持索引覆盖。

瞬间飞过,”我怎么这么好看,这么好看怎么办”

05

数据库内部利用索引是如何读取数据的?

搞了这么久,那这个索引查找数据的时候,是怎么个读取原理又是什么?

那这首先得说数据库中的读取数据单位,数据库中的数据是按照页读取的。默认一页的数据为16KB。而磁盘块(OS)默认为4KB

  • 1
    show global variables like 'innodb_page%';

    图片

那索引和数据都保存在节点里面,这个数据怎么个读法?

上面说到,数据库读取数据是根据页为单位,并且读的数据不满足1页或超过1页,那么也会读满1页。这也叫做预读

也就是说节点读取数据的大小应该控制在1页、2页、3页、4页等倍数页大小最为合适。

那你说说这个页吧!

img

图片

每个数据页中的数据,采用单向链表的形式进行连接。

各个页之间采用双向链表链接

图片

查找数据时是根据页内分组定义的。首先在插入数据时就会根据主键大小做好排序结构,并按照最大和最小进行分组。

最小虚拟数据独自一组,它拥有一条数据,就是最小数据。然后剩下的数据再分成一组,即最大数据为另一组。当进行数据插入的时,都是先插入到最大数据组,当最大数据组装满后在进行分裂

分组确立后,在进行数据查找的时就是根据二分查找法确定对应数据所在的槽位置,然后在使用记录头信息的next_record一条条进行查找。

当以(非主键)作为搜索条件:只能从最小虚拟数据记录,开始依次遍历单链表中的每条记录

1
所以,当写
  • 1
    2
    select * from nezha where name='nezha'
    这样没有进行任何优化的sql语句,默认会这样做:
  • 读取记录所在页的范围

  • 根据双向链表,找到所在页

  • 从所在页中查找相应的记录

  • 由于不是主键查询,就遍历所在页的单链表

06

索引就不命中?前提你得知道规则

使用索引当中,最核心的就是最左匹配原则,索引命中都是根据它来定义的。

图片

最左匹配原则

  • 索引可以的简单如单列 (a),也可以复杂如多列 (a,b,c,d),即联合索引

  • 如果是联合索引,那么key也由多个列组成,同时,索引只能用于查找key是否存在(相等),遇到范围查询 (>、<、BETWEEN、LIKE)等就不能进一步匹配了,后续退化为线性查找。因此,列的排列顺序决定了可命中索引的列数

  • 索引列不能是表达式的一部分,那样无法命中索引,例如

    • 1
      :SELECT  *   FROM  nezha  WHERE  id + 1 = 5;   date(create_time)='2020-03-05'

例如:

  • 如有索引 (a,b,c,d),查询条件 a=7 and b=8 and c>15 and d=32,则会在每个节点依次命中a、b、c,无法命中d。(c已经是范围查询了,d就没办法进行对比查找了)

总结:

索引在数据库中是一个非常重要的内容!

  • 最左前缀匹配原则。这是非常重要的原则,SQL查询都是基于它来。MySQL会一直向右匹配,直到遇到范围查询 (>,<,BETWEEN,LIKE)就停止匹配。
  • 也需要了解下,这个是数据库在内部的工作机制。
  • 索引的表现形式针对于不同的存储引擎,表现也不一样,并且2者之间的存储引擎区别也要掌握了解
  • 索引创建方式来自于建表前还是建表后。重点都是数据库再用后台线程创建与维护索引
  • B+Tree和Hash这2个特点还是需要注意,并且它们之间区别还未细讲。后面会针对面试问题,给大家补上来。