换一个角度看 树 B

大家好，我是小林。

大家背八股文的时刻，都知道 MySQL 里 InnoDB 存储引擎是驳回 B+ 树来组织数据的。

这点没错，但是大家知道 B+ 树里的节点里寄存的是什么呢?查问数据的环节又是怎样的?

这次，咱们从数据页的角度看 B+ 树，看看每个节点长啥样。

InnoDB 是如何存储数据的?

MySQL 允许多种存储引擎，不同的存储引擎，存储数据的方式也是不同的，咱们最经常常使用的是 InnoDB 存储引擎，所以就跟大家图解下InnoDB是如何存储数据的。

记载是依照行来存储的，但是数据库的读取并不以「行」为单位，否则一次性读取(也就是一次性 I/O 操作)只能处置一行数据，效率会十分低。

因此，InnoDB的数据是按「数据页」为单位来读写的，也就是说，当须要读一条记载的时刻，并不是将这个记载自身从磁盘读进去，而是以页为单位，将其全体读入内存。

数据库的 I/O 操作的最小单位是页，InnoDB 数据页的自动大小是 16KB，象征着数据库每次读写都是以 16KB 为单位的，一次性起码从磁盘中读取16K 的内容到内存中，一次性起码把内存中的 16K 内容刷新到磁盘中。

数据页包括七个局部，结构如下图：

这 7 个局部的作用如下图：

在 File Header 中有两个指针，区分指向上一个数据页和下一个数据页，衔接起来的页相当于一个双向的链表，如下图所示：

驳回链表的结构是让数据页之间不须要是物理上的延续的，而是逻辑上的延续。

数据页的关键作用是存储记载，也就是数据库的数据，所以重点说一下数据页中的 User Records 是怎样组织数据的。

数据页中的记载依照「主键」顺序组成单向链表，单向链表的特点就是拔出、删除十分繁难，但是检索效率不高，最差的状况下须要遍历链表上的一切节点能力成功检索。

因此，数据页中有一个页目录，起到记载的索引作用，就像咱们书那样，针对书中内容的每个章节设立了一个目录，想看某个章节的时刻，可以检查目录，极速找到对应的章节的页数，而数据页中的页目录就是为了能极速找到记载。

那 InnoDB 是如何给记载创立页目录的呢?页目录与记载的相关如下图：

页目录创立的环节如下：

从图可以看到，页目录就是由多个槽组成的，槽相当于分组记载的索引。而后，由于记载是依照「主键值」从小到大排序的，所以咱们经过槽查找记载时，可以经常使用二分法极速定位要查问的记载在哪个槽(哪个记载分组)，定位到槽后，再遍历槽内的一切记载，找到对应的记载，无需从最小记载开局遍历整个页中的记载链表。

以下面那张图举个例子，5 个槽的编号区分为 0，1，2，3，4，我想查找主键为 11 的用户记载：

看到第三步的时刻，或者有的同窗会不懂，假设某个槽内的记载很多，而后由于记载都是单向链表串起来的，那这样在槽外调找某个记载的期间复杂度不就是 O(n)了吗?

这点不用担忧，InnoDB 对每个分组中的记载条数都是有规则的，槽内的记载就只要几条：

B+ 树是如何启动查问的?

下面咱们都是在说一个数据页中的记载检索，由于一个数据页中的记载是有限的，且主键值是有序的，所以经过对一切记载启动分组，而后将组号(槽号)存储到页目录，使其起到索引作用，经过二分查找的方法极速检索到记载在哪个分组，来降落检索的期间复杂度。

但是，当咱们须要存储少量的记载时，就须要多个数据页，这时咱们就须要思考如何建设适宜的索引，能力繁难定位记载所在的页。

为了处置这个疑问，InnoDB 驳回了 B+ 树作为索引。磁盘的 I/O操作次数对索引的经常使用效率至关关键，因此在结构索引的时刻，咱们更偏差于驳回“矮胖”的 B+ 树数据结构，这样所须要启动的磁盘 I/O 次数更少，而且 B+ 树更适宜启动关键字的范畴查问。

更具体的为什么驳回 B+ 树作为索引的要素可以看我之前写的这篇：「索引为什么能提高查问功能?」

InnoDB 里的 B+ 树中的每个节点都是一个数据页，结构示用意如下：

经过上图，咱们看出 B+ 树的特点：

咱们再看看 B+ 树如何成功极速查找主键为 6 的记载，以上图为例子：

可以看到，在定位记载所在哪一个页时，也是经过二分法极速定位到蕴含该记载的页。定位到该页后，又会在该页内启动二分法极速定位记载所在的分组(槽号)，最后在分组内启动遍历查找。

汇集索引和二级索引

另外，索引又可以分红汇集索引和非汇集索引(二级索引)，它们区别就在于叶子节点寄存的是什么数据：

由于表的数据都是寄存在汇集索引的叶子节点里，所以 InnoDB存储引擎必定会为表创立一个汇集索引，且由于数据在物理上只会保留一份，所以聚簇索引只能有一个。

InnoDB 在创立聚簇索引时，会依据不同的场景选用不同的列作为索引：

一张表只能有一个聚簇索引，那为了成功非主键字段的极速搜查，就引出了二级索引(非聚簇索引/辅佐索引)，它也是应用了 B+树的数据结构，但是二级索引的叶子节点寄存的是主键值，不是实践数据。

二级索引的 B+ 树如下图，数据局部为主键值：

因此，假设某个查问语句经常使用了二级索引，但是查问的数据不是主键值，这时在二级索引找到主键值后，须要去聚簇索引中取得数据行，这个环节就叫作「回表」，也就是说要查两个B+ 树能力查到数据。不过，当查问的数据是主键值时，由于只在二级索引就能查问到，不用再去聚簇索引查，这个环节就叫作「索引笼罩」，也就是只要要查一个 B+树就能找到数据。

总结

InnoDB 的数据是按「数据页」为单位来读写的，自动数据页大小为 16KB。每个数据页之间经过双向链表的方式组织起来，物理上不延续，但是逻辑上延续。

数据页内蕴含用户记载，每个记载之间用单项链表的方式组织起来，为了放慢在数据页内高效查问记载，设计了一个页目录，页目录存储各个槽(分组)，且主键值是有序的，于是可以经过二分查找法的方式启动检索从而提高效率。

为了高效查问记载所在的数据页，InnoDB 驳回 b+ 树作为索引，每个节点都是一个数据页。

假设叶子节点存储的是实践数据的就是聚簇索引，一个表只能有一个聚簇索引;假设叶子节点存储的不是实践数据，而是主键值则就是二级索引，一个表中可以有多个二级索引。

在经常使用二级索引启动查找数据时，假设查问的数据能在二级索引找到，那么就是「索引笼罩」操作，假设查问的数据不在二级索引里，就须要先在二级索引找到主键值，须要去聚簇索引中取得数据行，这个环节就叫作「回表」。

关于索引的内容还有很多，比如索引失效、索引优化等等，这些内容我下次在讲啦!