前言

​ 本文为 mysql 专栏零碎索引的第一个大节的文章，索引蕴含的内容却是不少，为了让这些知识点不过分的沉积在一起，这里会将本文拆分为多个大节，并且后续的内容会逐步加深，本文更多是为索引的深刻了解进行概念性的讲述，蕴含索引的根底构造页目录和数据页的关联，以及索引如何依据页目录扩大主键目录，以及后续的索引页的设计介绍进行前置内容的解说。

概述

1. 索引页的根底构造：数据页和页目录的介绍，介绍对于页决裂的细节，他是 mysql 保护索引的一项重要个性，间接影响索引的查问效率。
2. 对于全表扫描的根底步骤了解，以及主键查问原理简略介绍，后续会做更加具体的介绍。
3. 对于索引的概览：主键索引和 BTree 索引的根底设计介绍。

索引的根底构造

数据页

​ 之前介绍过数据页的根本逻辑构造，在理解索引之前，咱们先来理解索引的物理构造，首先咱们须要晓得在磁盘上大抵如何存储：

​ 在磁盘文件的构造：数据页的每一行其实是一个二进制的非凡格局，每一个数据页蕴含指针，一个指向上一个数据页，一个指向下一个数据页，也就是说数据页是用双向链表进行串联的。总而言之，数据页是多个链表进行串联的，那么依照推理数据行其实也是链表的形式进行存储的，不过应用的是单向的链表，并且数据行是 依照主键从小到大进行排序 的。

页目录

​ 理解数据行的构造之后，接着就是和索引无关的构造，这个构造叫做页目录，为了保护数据页，每一个数据页的头部会蕴含页目录，依据数据行的主键进行寄存，数据行同时被扩散到不同的槽位 下来。能够说页目录是一个从小到大排序的一个动静数组，外面寄存的是键值对内容，键就是主键，值就是对应的数据页的数据行。

​ 针对下面数据页和页目录，咱们来看下整个页目录和数据页的的根底构造：

页决裂

​ 既然提到了页目录和数据页的构造，上面须要介绍一个和索引无关的重要个性：页决裂。页决裂说的是在传统的物理存储构造上，数据页之间都是应用双向链表进行串联的，数据页内的数据行是单向链表的模式进行串联，比方像下面这样，此时如何咱们新插入一条数据，会把数据依照链表的模式串联起来，并且如果主键是自增的状况下，他会依照主键自增的程序进行链接。

​ 下面的状况在主键自增的状况下通常没有什么问题。然而如果你的主键不是自增的，比方当初你插入 12，下一次你插入 8，就会呈现问题了，此时就会很页决裂，对于页决裂的内容，能够看上面的格局：

什么是页决裂？

简略来讲，在一个多链表链接的多个数据页外面，页决裂会把一个主键较大的值移动到新的的数据页，而新插入的主键较小的值会移动到之前的数据页

​ 1. 比方如果咱们不依照自增的形式增长主键，就会呈现上面的形式。

2. 接着，依据页目录的保护规定，须要对于数据也进行挪移的动作，其实挪移的规定很简略：把主键更大的值挪到更新的数据页，把更小的值挪到一起。

页决裂对于 mysql 的索引有哪些影响?

页决裂的行为会影响 mysql 的索引，可能会呈现 mysql 找不到数据所在的页呈现全表扫描

全表扫描

​ 理解了数据页和页目录的根底构造之后，咱们来看下全表扫描是如何解决的，全表扫描其实是数据页一直加载到缓冲区的过程，这个过程在之前的文章有过介绍这里不做过多赘述，在没有索引的状况下，数据页加载到缓冲区只能依照数据页的链表一个个拜访，比如说加载第一个数据页没有找到数据，就加载第二个，没有第二个就加载第三个，以此类推，最初找到咱们想要的数据为止，如果数据页非常多然而须要的数据零散的散布在少数的数据页上，这样的查找效率是非常低的。

​ 最初咱们针对索引做一个简略的介绍，这就好比你去图书馆找书，你要把所有的货架都扫完了能力找到你要的书，这样未免就太慢了，页目录就如同一个小册子，标记那一个货架有你要的书，而后找到对应的货架去扫描就行了。。

​ 为了放慢这个查找速度，咱们最先想到的是主键查问的形式：

主键查问的原理

​ 其实晓得了页目录之后，咱们就晓得主键是如何查找的，主键是依照从小到大的程序排序的，查找主键其实就是二分查找的形式依照页目录的排序进行查找找到对应的主键，而后取出对应的的槽位并且找到对应的数据页进行扫描，而数据页之间也是链表查找，找到数据页之后找到对应的数据行就行。这就是主键查问的大抵思路。

索引介绍

主键索引

​ 什么是主键索引？之前的页决裂咱们理解了数据页会在主键上把主键的内容进行排序。而主键索引实际上就是针对主键制作一个主键目录，把每个数据页的页号，数据页最小的主键值放大一起，组成一个索引，这样通过找到最小的主键号就能够疾速的找到对应的数据页和数据行了。

​ 主键索引的结构图如下：

BTree 索引（重点）

索引页的设计模式

​ 接下来就是本文的重点也是 mysql 重要的 btree 索引，在具体的理解之前，咱们须要理解一下他的索引设计构造，也就是 索引页。

​ 什么是索引页？大家能够思考一下，如果把索引页和数据页离开成为独自的构造，其实是非常不不便的，这样增大了磁盘扫描和数据加载到内存的开销，并且数据页太多了之后存储页非常不不便，所以其实索引也是被设计为“数据页”的，只不过存储的内容和个别的数据页不一样，存储的是 每个数据页的最小主键。这里为了更好的了解，咱们从逻辑上把他们拆分为两种表现形式，上面咱们用结构图来示意索引页的设计模式:

​ 然而遇到一个问题，如果把索引页全都是平级的关系，会不晓得找到哪一个索引页 ，所以在索引页存在上下级的关系，接下来咱们又能够把索引页多加一个层级进去，在更高的索引层级里，保留了 每个索引页的索引页的号码和索引页里的最小主键值：

​ 咱们假如索引页如下面的设计，首先索引要先从 35 找到索引页 1，而后应用索引页 1 的二分查找定位到指标的索引页，找到比方在数据页 8 外面有数据，而后找到数据页 8 的数据行进行扫描，找到最初的数据。因为在存储的过程中一直的决裂出一个层级，能够发现这种派生的形式其实就是组成一个 bTree 的树。

​ 以上就是对于 BTree 索引的大抵设计概览，当然理论的细节远远没有下面说的简略，然而下面的内容能够根本理解对于索引的设计规定。

总结

​ 这一节更像是对于 mysql 索引的底层入门介绍，然而内容并不算十分复杂。

写在最初

​ mysql 的索引第一篇，对于索引更多的内容将会在后续的大节持续深刻。