本篇内容，是自己查阅国内外各类作者的文章和视频后，对此作出的总结。如果文章有错漏的中央，欢送大家斧正。

这篇文章的次要内容为，推导出在关系型数据库中，为何选用 B + 树作为索引实现。

磁盘如何存储数据

对于机械硬盘，磁盘内至多蕴含一个盘片。盘片上有一圈圈同心圆，相邻两个同心圆围成每个环形被称为磁道(track)，也就是图片中粉色局部。同时，从磁盘转轴往外辐射出一条条辐线，辐线与磁道相交的中央，造成一个个弧形段，被称为扇区(Sector)，也就是图片中粉色环和蓝色扇形相交的局部。如果机械硬盘蕴含多个盘片，则不同盘片上同一地位的磁道组成一个柱面（Cylinder），不过这个概念对于这篇文章来说不太重要。

重点是，扇区是磁盘读写的最小单位，这是一个物理单位 ，通常来说，一个扇区的大小是 512B，这取决于机械硬盘的制造商。不过只管硬盘读写的最小单位是扇区， 但对于操作系统来说，读写硬盘的最小单位是块（Block）/ 簇（Cluster），这是一个逻辑单位 ，块是 Linux 的叫法，簇是 Windows 的叫法。 一个块蕴含多个间断的扇区，这个蕴含的扇区数是可调的，每个分区的块大小能够是不同的，通常为 8 个，也就是一个块的大小为 4kiB。之所以操作系统要减少块这个概念，起因很显著是为了将硬盘的物理设计和操作系统的逻辑设计解耦，也给予用户更多的抉择空间。因为对于机械硬盘来说，随机读取不同磁道上扇区是十分迟缓的，但读取间断的扇区的速度是十分快的。所以，一个块蕴含越多扇区，每次能读取到的内容就会更多。然而因为块是操作系统中最小的读写单位，所以，一个文件即便什么内容也没有，也将会占用一个块。若零碎中有很多小文件，块的大小设计得十分大，就会节约很多磁盘空间。

那程序是如何从硬盘读取内容的呢？程序读取数据只可能通过内存读取，而内存也有最小的读写单位，就是页（Page），通常一个页的大小是 4kiB。程序要读取文件，操作系统要从硬盘上读取整数块的数据，填入整数页的内存中，供程序应用。之所以要减少页这个概念，起因很显著是为了屏蔽不同分区上块的大小的不同，对程序读取文件造成的影响。

理解下面的前提后，咱们晓得一个事实，程序通过操作系统从磁盘读取一个字节，至多须要读取一个块（4kiB)。硬盘上的一个字节，能够示意为块号 + 块内偏移量。

实际上，对于 InnoDB 存储引擎来说，读写是依照“索引页节点”来的。此“页”并非操作系统中的“页”，而是存储引擎所应用的数据结构，通常设置为 16kiB，你能够在 MySQL 内通过 SHOW VARIABLES LIKE 'innodb_page_size%' 晓得以后的页设置大小。不过这并不影响整篇文章的论断推导。

为何须要应用索引

当初咱们假如有这样一张数据表，它蕴含 id，姓名两个字段，数据大小如下。

嗯，名字字段的大小为 1020B，仅仅是为了不便计算。假如咱们这张表有 100 条数据。

那咱们须要存储它应用到多少个硬盘块呢？很显著，(100*(1020+4))/4096=25。也就是 25 个块。

那当咱们从硬盘中读取某个 id 值对应的姓名，那该怎么办呢？一个块内的扇区在硬盘碟片上是间断的，但一个文件被分成一个个块贮存在碟片上时，是随机的，咱们没方法通过每条数据的大小，在硬盘上间接跳转。所以，如果咱们要找到某个 id，就须要从头开始，读取至多 1 个，至少 25 个块。

这种状况就像读取一本没有目录的书一样，每次都须要遍历一遍能力找到所需内容，为了防止这种状况，咱们能够给像给书加上目录一样，给表加上索引。

咱们当初设计一张索引表，蕴含 id 和指针，这里咱们假如指针大小为 6，其实这也是 innodb 存储引擎的指针大小。

而后咱们就构建出上面这张表，很显著，这张表的大小为 1000B，只需应用一个块就能存储。

有了这张表后，咱们只须要读取一张索引表，而后再通过指针指向的磁盘块号和偏移量即可找到目标数据。只须要读取 2 个块。

顺便一提，这种索引表存储数据地址的形式也叫非聚簇索引，是 MyISAM 存储引擎所采纳的计划。

如果索引表也很大怎么办

假如咱们这个表有 1 万条数据，那索引表就会占用 25 个块。那又没有什么方法进步呢？那咱们能够为索引再建设一个索引。

索引的索引，能够设计为，某个范畴内的 id 所对应的磁盘块号。

比方，在咱们索引表中，每条记录占用 10B，所以一个块能够存 409 条索引。咱们能够设计这样的索引的索引，id 为 1 -409 的跳转到块 111，id 为 410-818 的跳到块 222，以此类推，咱们只须要读取索引的索引，依据 id 即可跳转到相应范畴的索引表上，不须要残缺读取整个索引表。

如果用图示意的话就是大略这样，画得不好，凑合着看吧。那咱们这张索引的索引，会占用多少空间呢？很显著，只须要((10000/409)*10)/4096=0.0596…。所以，咱们最初读取表中的数据，只须要读取 3 个块，效率大大晋升了。

如何让建设索引、索引的索引的这个过程更加自动化

如果索引的索引也很大呢，那很显著是须要设计索引的索引的索引了，然而如何让这个过程更加智能和自动化呢？

其实从下面那幅图，咱们大略能够看出些端倪。须要获取某个数据，要从最上层的索引开始比拟查找，最初深刻到最上层节点，即可取得相应数据。这很显著就是一种树。

那么，该抉择什么类型的树比拟好呢？常见的用于搜寻的树，有二叉搜寻树（BST），AVL 树，红黑树，B 树，B+ 树。

其实从下面的推论，咱们能够看出，优化索引的目标，最终是为了缩小磁盘读取的块数。因为磁盘 IO 对于 CPU 运算、内存读取来说，都太慢了，是数据库的瓶颈。而对于常见的各种二叉树，他们每个节点只能有两个子节点，如果应用二叉树构建索引树，那将其存储到磁盘后，每个块只能蕴含一个索引键。这会带来两个问题，1，一个块的空间不止能够存储一个索引键，块内其余的空间被节约了。2，这棵索引树会比拟高，则将会导致较多的硬盘读取次数。（如果你问我为什么一个块不能存储多个节点，那我不晓得了)

所以，为了缩小磁盘读取次数，要尽可能升高树高，而升高树高就须要用到多路搜寻树，常见的多路搜寻树有 B 树和 B + 树。

B 树

这里咱们先说一下 B 树，前面再来议论 B + 树。B 树是一种多路均衡搜寻树。
对于一棵 m 阶层 B 树，有这样几个定义：

1. 每个节点最多能有 m 棵子树
2. 每个非叶非根节点，至多有 celi(m/2) 棵子树（celi 为向上取整）
3. 如果根节点不同时是叶节点，那至多有 2 棵子树
4. 有 k 个子树的节点，领有 k - 1 个关键字
5. 所有叶节点都在同一层

咱们能够去这个网站 Data Structure Visualizations，察看 B 树的插入、删除、决裂和合并节点的过程。这里咱们并不具体探讨 B 树的决裂、合并节点算法。

这里咱们有一棵 3 阶 B 树，它是这样的。咱们能显著看出，因为分叉多了，整棵树能够变得更矮。如果每个节点代表一个硬盘块，能够看出，须要读取的磁盘块数起码 1 块，最多 3 块。同时所有叶节点都在同一层，这意味着不会有某个查问，须要多于 logM(N) 的查问工夫。这里的 M 是 B 树上每个节点的 均匀叉数，N 为数据量, 这论断能够从二叉搜寻树推导而出。

B+ 树

B+ 树是 B 树的升级版。对于 B + 树的定义，实际上在不同教材、书籍里，细节上会有不同 。思考到 B 树及其各种变体（B+,B* 树）本就是为了在工程上实际应用的，不仅不同教材上的形容不同，不必数据库存储引擎也会有各种变体实现。因而短少严格的学术定义。
对于一棵 m 阶层 B + 树，有这样几个定义：

1. 每个节点最多能有 m 棵子树
2. 每个非叶非根节点，至多有 celi(m/2) 棵子树（celi 为向上取整）
3. 如果根节点不同时是叶节点，那至多有 2 棵子树
4. 所有叶节点都在同一层
   目前为止这都和 B 树的定义一样
5. 所有的数据，都贮存于叶节点。且依照顺序排列，通过指针相连接
6. 所有非叶节点，只是作为索引，并不贮存数据

接下来是比拟有争议和让人困惑的局部：

对于国外的大部分教材来说，有 k 棵子树的节点，领有 k-1 个关键字。这和 B 树很类似，很容易了解。

对于 InnoDB 引擎的索引树实现，和国内的大部分教材来说（比方严蔚敏的《数据结构》）来说，有 k 棵子树的节点，领有 k 个关键字。同时，每个非叶节点蕴含其子树的最大（或最小）关键字。这种 B + 树是长这样子的。这种设计的 B + 树，自己其实不太了解它的构建过程细节。考研里也仅要求理解其基本概念和性质，短少相干教材形容。不过这些差别并不是大问题，不影响接下来的论断推导。为了不便解说和画图，上面我依然应用国外教材定义的 B + 树。

这里咱们有一棵 3 阶 B 树，它是这样的。能够看出，因为所有数据都在叶节点，因而拜访任何一个数据都须要拜访 logM(N) 次（M 仍是均匀分叉数、N 是数据量）。同时，因为非叶节点都只是索引，所有的数据都在叶节点上，因而有肯定的数据冗余，造成某些状况下，同样的数据量和阶数，B+ 树会比 B 树高。

为什么抉择 B + 树

仿佛 B + 树看上去比 B 树性能要差，那为何它是数据库索引的常见实现？

咱们关注 B 树和 B + 树最大的不同点，即

5. 所有的数据，都贮存于叶节点。且依照顺序排列，通过指针相连接
6. 所有非叶节点，只是作为索引，并不贮存数据

对于 5。因为所有的数据都被程序地排列于叶节点层上，如果对 B + 树索引进行范畴查问和全表扫描，将会是很容易的事件。而对于 B 树，须要进行中序遍历，这将可能造成更多的随机 IO，以及更简单的算法实现。

对于 6。这个是最要害的一点。因为 B + 树中非叶节点只是作为索引，不蕴含数据。所以对于每个磁盘来说，应用 B + 树，每个块能够存入更多的关键字，这将使得索引树变得更矮。

假如 B 树和 B + 树都应用 4 字节的主键和 6 字节的指针，为了不便计算，要害字数和子树数雷同。那在一个 4kiB 的磁盘块里。B+ 树能存 4096/(4+6)=409 条索引，B 树因为每个节点蕴含数据，因而至多须要一个指向数据的指针，所以一个块只能存 4096/(4+6+6)=256 条索引。能看出，应用 B + 树，索引树能够变得更加矮，效率大略比 B 树高了一倍。因而，即便实践上 B + 树在同阶状况下，树可能比 B 树高，但理论贮存到磁盘上，B+ 树能取得更大的阶数。

此外，B+ 树的查问复杂度是稳固logM(N)，不同于 B 树的起码1，最大logM(N)，可能有读者对此会有疑难，为什么须要有稳定性。其实自己也有这样的疑难，集体参考各个博主的观点和本人的思考后。集体认为最大的收益在于数据库管理系统的查问优化。大部分数据管理系统，比方 MySQL，会对查问进行隐式的优化，决定是否走索引，走哪个索引。进行一条查问语句，可能有多种查问形式，MySQL 会在多种形式中，比拟各种老本花销，最初抉择一种它认为最佳的计划。而 B + 树的稳固查问复杂度，使得计算成本变得可预期。

额定的知识点

InnoDB 中，主键索引树通常有多高？

在 InnoDB 中，贮存节点的单位并不是磁盘块，而是 InnoDB 所设计的“页”。同时，InnoDB 应用的是聚簇索引，即叶子节点蕴含数据表中整行的数据。文章结尾讲过，这个页大小通常是 16kiB。而对于常见的 INT 型 id 主键，需 4 个字节。InnoDB 中指针须要 6 个字节。

因而，对于以 INT 作为主键的状况下，假如每条数据大小为 1kiB。InnoDB 每个页能存 1638 条索引，16 条数据。所以，树高为 1 时，能存 16 条数据，这个状况下，只有一个页充当根或叶节点。树高为 2 时（只有根和叶节点），能存 1638*16 条数据。树高为 3 时，能存 1638*1638*16 条数据，树高为 4 时，能存 1638*1638*1638*16 条数据。当然这个是每个节点都达到最大阶数的状况下的理论值，理论状况会小一点，不过无关紧要，因为能看出树高为 3 时，就曾经能存储 4 千万条数据了。

InnoDB 每次搜寻索引，须要多少次磁盘 IO

树高多少，就须要读取多少次节点。大部分博客都会说硬盘 IO 次数等同于树高，但这只会在树节点大小等同于磁盘块数的状况下成立。InnoDB 中，数据页大小为 16kiB，根页常驻内存。操作系统中常见的块大小为 4kiB。因而实践上，真正的磁盘 IO 数量应该为 树高 *(数据页大小 / 块大小）-1，- 1 是因为根页常驻内存。

参考

• [1] Data Structure Visualizations
• [2] 10.2 B Trees and B+ Trees. How they are useful in Databases
• [3] B+ 树查问的稳定性为什么重要？
• [4] B+Tree index structures in InnoDB
• [5] B+Trees – How SQL Server Indexes are Stored on Disk
• [6] How Database B-Tree Indexing Works
• [7]批改 Innodb 的数据页大小以优化 MySQL 的办法
• [8]MySQL innodb_page_size