背景

我置信大家在数据库优化的时候都会说到索引，我也不例外，大家也基本上能对数据结构的优化答复个一二三，以及页缓存之类的都能扯上几句，然而有一次阿里P9的一个面试问我：你能从计算机层面开始说一下一个索引数据加载的流程么？（就是想让我聊IO）

我当场就逝世了....因为计算机网络和操作系统的基础知识真的是我的盲区，不过前面我恶补了，废话不多说，咱们就从计算机加载数据聊起，讲一下换个角度聊索引。

如果感觉看完文章有所播种的话，能够关注我一下哦
知乎：秃顶之路
b站：linux亦有归途
每天都会更新咱们的公开课录播以及编程干货和大厂面经
或者间接点击链接c/c++ linux服务器开发高级架构师
来课堂上跟咱们讲师面对面交换
须要大厂面经跟学习纲要的小伙伴能够加群973961276获取

注释

MySQL的索引实质上是一种数据结构

让咱们先来理解一下计算机的数据加载。

磁盘IO和预读：

先说一下磁盘IO，磁盘读取数据靠的是机械运动，每一次读取数据须要寻道、寻点、拷贝到内存三步操作。

寻道工夫是磁臂挪动到指定磁道所须要的工夫，个别在5ms以下；

寻点是从磁道中找到数据存在的那个点，均匀工夫是半圈工夫，如果是一个7200转/min的磁盘，寻点工夫均匀是600000/7200/2=4.17ms；

拷贝到内存的工夫很快，和后面两个工夫比起来能够忽略不计，所以一次IO的工夫均匀是在9ms左右。听起来很快，但数据库百万级别的数据过一遍就达到了9000s，显然就是劫难级别的了。

思考到磁盘IO是十分昂扬的操作，计算机操作系统做了预读的优化，当一次IO时，不光把以后磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为当计算机拜访一个地址的数据的时候，与其相邻的数据也会很快被拜访到。

每一次IO读取的数据咱们称之为一页(page)，具体一页有多大数据跟操作系统无关，个别为4k或8k，也就是咱们读取一页内的数据时候，实际上才产生了一次IO。

（忽然想到个我刚毕业被问过的问题，在64位的操作系统中，Java中的int类型占几个字节？最大是多少？为什么？）

那咱们想要优化数据库查问，就要尽量减少磁盘的IO操作，所以就呈现了索引。

索引是什么？

MySQL官网对索引的定义为：索引(Index)是帮忙MySQL高效获取数据的数据结构。

MySQL 中罕用的索引在物理上分两类，B-树索引和哈希索引。

本次次要讲BTree索引。

BTree索引

BTree又叫多路均衡查找树，一颗m叉的BTree个性如下：

  • 树中每个节点最多蕴含m个孩子。
  • 除根节点与叶子节点外，每个节点至多有[ceil(m/2)]个孩子（ceil()为向上取整）。
  • 若根节点不是叶子节点，则至多有两个孩子。
  • 所有的叶子节点都在同一层。
  • 每个非叶子节点由n个key与n+1个指针组成，其中[ceil(m/2)-1] <= n <= m-1 。
![](data:image/svg+xml;utf8,<?xml version="1.0"?><svg xmlns="http://www.w3.org/2000/svg" version="1.1" width="800" height="600"></svg>)

这是一个3叉（只是举例，实在会有很多叉）的BTree结构图，每一个方框块咱们称之为一个磁盘块或者叫做一个block块，这是操作系统一次IO往内存中读的内容，一个块对应四个扇区，紫色代表的是磁盘块中的数据key，黄色代表的是数据data，蓝色代表的是指针p，指向下一个磁盘块的地位。

来模仿下查找key为29的data的过程：

1、依据根结点指针读取文件目录的根磁盘块1。【磁盘IO操作1次】

2、磁盘块1存储17，35和三个指针数据。咱们发现17<29<35，因而咱们找到指针p2。

3、依据p2指针，咱们定位并读取磁盘块3。【磁盘IO操作2次】

4、磁盘块3存储26，30和三个指针数据。咱们发现26<29<30，因而咱们找到指针p2。

5、依据p2指针，咱们定位并读取磁盘块8。【磁盘IO操作3次】

6、磁盘块8中存储28，29。咱们找到29，获取29所对应的数据data。

由此可见，BTree索引使每次磁盘I/O取到内存的数据都施展了作用，从而进步了查问效率。

然而有没有什么可优化的中央呢？

咱们从图上能够看到，每个节点中不仅蕴含数据的key值，还有data值。而每一个页的存储空间是无限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查问时的磁盘I/O次数，进而影响查问效率。

B+Tree索引

B+Tree是在B-Tree根底上的一种优化，使其更适宜实现外存储索引构造。在B+Tree中，所有数据记录节点都是依照键值大小程序寄存在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样能够大大加大每个节点存储的key值数量，升高B+Tree的高度。

![](data:image/svg+xml;utf8,<?xml version="1.0"?><svg xmlns="http://www.w3.org/2000/svg" version="1.1" width="800" height="600"></svg>)

B+Tree绝对于B-Tree有几点不同：

非叶子节点只存储键值信息， 数据记录都寄存在叶子节点中， 将上一节中的B-Tree优化，因为B+Tree的非叶子节点只存储键值信息，所以B+Tree的高度能够被压缩到特地的低。

具体的数据如下：

InnoDB存储引擎中页的大小为16KB，个别表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也个别为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大略存储16KB/(8B+8B)=1K个键值（因为是估值，为不便计算，这里的K取值为〖10〗^3）。

也就是说一个深度为3的B+Tree索引能够保护10^3 10^3 10^3 = 10亿 条记录。（这种计算形式存在误差，而且没有计算叶子节点，如果计算叶子节点其实是深度为4了）

咱们只须要进行三次的IO操作就能够从10亿条数据中找到咱们想要的数据，比起最开始的百万数据9000秒不晓得好了多少个华莱士了。

而且在B+Tree上通常有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环构造。所以咱们除了能够对B+Tree进行主键的范畴查找和分页查找，还能够从根节点开始，进行随机查找。

数据库中的B+Tree索引能够分为汇集索引（clustered index）和辅助索引（secondary index）。

下面的B+Tree示例图在数据库中的实现即为汇集索引，汇集索引的B+Tree中的叶子节点寄存的是整张表的行记录数据，辅助索引与汇集索引的区别在于辅助索引的叶子节点并不蕴含行记录的全副数据，而是存储相应行数据的汇集索引键，即主键。

当通过辅助索引来查问数据时，InnoDB存储引擎会遍历辅助索引找到主键，而后再通过主键在汇集索引中找到残缺的行记录数据。

![](data:image/svg+xml;utf8,<?xml version="1.0"?><svg xmlns="http://www.w3.org/2000/svg" version="1.1" width="800" height="600"></svg>)

不过，尽管索引能够放慢查问速度，进步 MySQL 的解决性能，然而过多地应用索引也会造成以下弊病：

  • 创立索引和保护索引要消耗工夫，这种工夫随着数据量的减少而减少。
  • 除了数据表占数据空间之外，每一个索引还要占肯定的物理空间。如果要建设聚簇索引，那么须要的空间就会更大。
  • 当对表中的数据进行减少、删除和批改的时候，索引也要动静地保护，这样就升高了数据的保护速度。
留神：索引能够在一些状况下减速查问，然而在某些状况下，会升高效率。

索引只是提高效率的一个因素，因而在建设索引的时候应该遵循以下准则：

  • 在常常须要搜寻的列上建设索引，能够放慢搜寻的速度。
  • 在作为主键的列上创立索引，强制该列的唯一性，并组织表中数据的排列构造。
  • 在常常应用表连贯的列上创立索引，这些列次要是一些外键，能够放慢表连贯的速度。
  • 在常常须要依据范畴进行搜寻的列上创立索引，因为索引曾经排序，所以其指定的范畴是间断的。
  • 在常常须要排序的列上创立索引，因为索引曾经排序，所以查问时能够利用索引的排序，放慢排序查问。
  • 在常常应用 WHERE 子句的列上创立索引，放慢条件的判断速度。

当初大家晓得索引为啥能这么快了吧，其实就是一句话，通过索引的构造最大化的缩小数据库的IO次数，毕竟，一次IO的工夫真的是太久了。。。

总结

就面试而言很多常识其实咱们能够很容易就把握了，然而要以学习为目标，你会发现很多货色咱们得深刻到计算机根底上能力发现其中神秘，很多人问我怎么记住这么多货色，其实学习自身就是一个很无奈的货色，既然咱们不能不学那为啥不好好学？去学会享受呢？最近我也在恶补根底，前面我会开始更新计算机根底和网络相干的常识的。