本文转载自微信公众号《三太子敖丙》，作者：三太子敖丙。转载本文请联系三太子敖丙公众号。背景相信大家在优化数据库的时候都会说到索引，我也不例外。数据结构优化基本可以回答一二三，还有几句页面缓存，但是有个阿里P9的面试问我：能不能从计算机层面说说加载索引数据的过程？（就是要我说IO）我当场死了。。。因为计算机网络和操作系统的基础知识真的是我的盲区，不过后面会补上的，废话不多说，咱说说从计算机加载数据，换个角度说说索引。字面意思MySQL索引本质上是一种数据结构我们先来了解一下计算机的数据加载。磁盘IO与预读：先说磁盘IO。磁盘通过机械运动读取数据。每次读取数据都需要三个步骤：查找、查找、复制到内存。寻道时间是磁臂移动到指定磁道所需要的时间，一般小于5ms；寻道点是从轨迹中寻找数据存在的点，平均时间为半圈。如果是7200转的盘，平均查找时间为600000/7200/2=4.17ms；copy到内存的时间很快，跟前两次相比可以忽略不计，所以一次IO平均耗时9ms左右。听起来很快，但是数据库的百万数据一下pass就达到了9000s，这显然是灾难级的。考虑到磁盘IO是一个非常昂贵的操作，计算机操作系统对预读进行了优化。当执行IO时，不仅将当前磁盘地址的数据，而且将相邻的数据读入内存缓冲区。因为当计算机访问某个地址的数据时，与其相邻的数据也会被快速访问。每个IO读取的数据称为一个页面。页面的具体大小与操作系统有关，一般为4k或8k。也就是说，当我们读取一个页面中的数据时，它实际上发生了。IO一次。（突然想到刚毕业被问到的一个问题，在64位操作系统中，Java中的int类型占多少字节？最大是多少？为什么？）然后我们要优化数据库查询，我们一定要尽量减少磁盘IO操作，这样索引才会出现。什么是索引？MySQL官方对索引的定义是：索引（Index）是一种帮助MySQL高效获取数据的数据结构。MySQL中常用的索引在物理上分为两类，B树索引和散列索引。这次主要讲BTree索引。BTree索引BTree也称为多路平衡搜索树。m-forkBTree的特点如下：树中的每个节点最多包含m个子节点。除根节点和叶节点外，每个节点至少有[ceil(m/2)]个子节点（ceil()向上取整）。如果根节点不是叶节点，则它至少有两个孩子。所有叶节点都处于同一级别。每个非叶节点由n个键和n+1个指针组成，其中[ceil(m/2)-1]<=n<=m-1。这是一个有3个叉子的BTree结构图（只是举个例子，现实中会有很多叉子）。每个块称为磁盘块或块块。这是操作系统一次IO读入内存的内容，一个block对应四个扇区，紫色代表磁盘块中的datakey，黄色代表数据data，蓝色代表指针p，指向下一个磁盘块的位置。模拟查找key为29的数据的过程：1.根据根节点指针读取文件目录的根磁盘块1。【磁盘IO操作一次】2、磁盘块1存储17、35和三个指针数据。我们发现17<29<35，所以我们找到指针p2。3、根据p2指针，定位并读取磁盘块3。【两次磁盘IO操作】4、磁盘块3存储26、30和三个指针数据。我们发现26<29<30，所以我们找到指针p2。5、根据p2指针，我们定位并读取磁盘块8。【磁盘IO操作3次】6、将28和29存储到磁盘块8中，我们找到29，得到29对应的数据。可以看出BTree索引使得每次磁盘I/O取内存中的数据发挥作用，从而提高查询效率。但是有什么可以优化的吗？从图中我们可以看出，每个节点不仅包含数据的键值，还包含数据值。每个页面的存储空间是有限的。如果data数据很大，那么每个节点（也就是一个页??面）可以存放的key数量就会很少。当存储的数据量很大时，也会导致B-树的深度越大，查询时的磁盘I/O次数就越大，进而影响查询效率。B+Tree索引B+Tree是在B-Tree的基础上进行优化，使其更适合实现外部存储的索引结构。在B+Tree中，所有的数据记录节点都按照键值的顺序存储在同一层的叶子节点上，非叶子节点上只存储键值信息，可以大大增加键值的个数由每个节点存储，降低B+Tree的高度。与B-Tree相比，B+Tree有几点不同：非叶子节点只存储key-value信息，数据记录存储在叶子节点中。上一节的B-Tree进行了优化，因为B+Tree的非叶子节点只存储key-value信息，所以B+Tree的高度可以压缩到特别低的水平。具体数据如下：InnoDB存储引擎中page的大小为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。）我们只需要进行3次IO操作，就可以从10亿条中找到我们想要的数据数据的。比起前百万数据和9000秒不知道有多少华莱士恢复过来了。而且B+Tree上通常有两个头指针，一个指向根节点，一个指向key最小的叶子节点，所有叶子节点（即数据节点）之间有链环结构.因此，除了在B+Tree上进行主键的范围查找和分页查找外，我们还可以从根节点开始进行随机查找。数据库中的B+Tree索引可以分为聚集索引（clusteredindex）和辅助索引（secondaryindex）。上面B+Tree实例图在数据库中的实现就是聚簇索引。聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引和聚簇索引的区别在于辅助索引的叶子节点不包含行记录的所有数据，而是存储对应行数据的聚簇索引键，即主键。当通过辅助索引查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后使用主键在聚簇索引中找到完整的行记录数据。但是，索引虽然可以加快查询速度，提高MySQL的处理性能，但是过度使用索引也会带来以下弊端：创建索引和维护索引都需要时间，而且这个时间随着数据量的增加而增加。除了数据表占用的数据空间外，每个索引还占用一定的物理空间。如果要建立聚簇索引，需要的空间就更大了。在对表中的数据进行增删改查时，索引也要动态维护，降低了数据维护的速度。注意：索引在某些情况下可以加快查询速度，但在某些情况下会降低效率。建立索引只是提高效率的一个因素，因此在建立索引时应遵循以下原则：在需要经常搜索的列上建立索引可以加快搜索速度。在列上创建索引作为主键，强制列的唯一性，组织表中数据的排列结构。在表连接中经常使用的列上创建索引，这些列主要是一些外键，可以加快表连接的速度。根据范围在经常需要查找的列上建立索引。因为索引是排序的，所以指定范围是连续的。在经常需要排序的列上创建索引。因为索引已经排序了，所以在查询的时候可以利用索引的排序来加快排序查询的速度。对频繁使用WHERE子句的列创建索引，加快条件判断。现在大家知道为什么索引可以这么快了吧。其实就是一句话，通过索引的结构来尽量减少数据库的IO次数。毕竟一次IO的时间实在是太长了。..总结就面试而言，我们其实可以轻松掌握很多知识，但是为了学习，你会发现很多东西。我们必须深入计算机基础才能发现其中的奥秘。很多人问我怎么记住那么多东西，其实学习本身就是一件很无奈的事情。既然要学习，何不好好学习呢？学会享受吗？最近也在搞基础，后面开始更新电脑基础和网络相关的知识。
