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

这篇文章的次要内容为，推导出在关系型数据库中，为何选用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