MySQL的B树与B+树

一、B树

1.B树特点

1. 所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
4. 在关键字全集内做一次查找,性能逼近二分查找；

2.B树查找

我们来看看B-树的查找，假设每个节点有 n 个 key值，被分割为 n+1 个区间，注意，每个 key 值紧跟着 data 域，这说明B-树的 key 和 data 是聚合在一起的。一般而言，根节点都在内存中，B-树以每个节点为一次磁盘 IO，比如上图中，若搜索 key 为 25 节点的 data，首先在根节点进行二分查找（因为 keys 有序，二分最快），判断 key 25 小于 key 50，所以定位到最左侧的节点，此时进行一次磁盘 IO，将该节点从磁盘读入内存，接着继续进行上述过程，直到找到该 key 为止。

二、B+树

B+树的叶子节点就是数据页

不是所有的行数据都在叶子节点上，只是父节点中线索指向的那些节点在树上，如上图，两个灰色的其实就不再树上。

所以行数据的组织方式是以page为最小单位，按照链表的方式来组织的。非叶子节点上的线索指向的叶子节点就算是在树上。而对于也字节点，一个page内是存放了多条行记录的，这多条记录是按照索引从小大大排序的，所以查询的过程首先是根据B+树索引定位到具体的page，然后page内使用二分法去找具体的行数据。

1.B+树特点

B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于:

1. 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
2. 为所有叶子结点增加了一个链指针
3. 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列

2.叶子节点与内部节点

一般B+树的叶节点和内节点大小相同，为一页 (16k)，B-树的每个节点大小相同的，为一页 (16k)

非叶子节点就是一个16k大小的page，所以对于一棵树能存多少数据，主要就看非叶节点能存下多少个[主键ID+指针]

主键ID是一个bigint(8字节)，nnodb中一个指针是6字节长度，所以[主键ID+指针]总共就占14字节。

一个16K大小的节点可以存下的[主键ID+指针]个数=16K/14=16384/14=1170，也就是说一个高度=2的B+树可以放下1170个叶子节点，即1170个用于存放行数据的page，即可以存放的行数据的大小=1170*16K=18720K=1.8M，准确的说这是树上的，还有很多不在树上的，所以实际能放下的数据不止1.8M。

分析高度=3，即有两层非叶子节点的B+树，能存放多少数据。根节点的16k的page可以存放16k/14=1170个[主键ID+指针]，即第二层就可以有1170个page。所以总共树上可以放的叶子节点的个数=1170*1170=1368900，所以能放下的数据=1368900*16K=21902400K=21G。同理，因为不是所有的行数据都在树上，所以高度=3的B+树不止放下21G的数据的。

高度=4的，那么树上可以存下的叶子节点=117011701170=1601613000个，所以能存下的数据=1601613000*16K=25.6T。同理，实际存下的数据是可以不止这个量的

所以，在实际中，绝大部分的表的索引树的高度都不会超过4。

一个page内还有一些其他的数据，如next指针，LSN等，所以说一个page的16K不完全都拿来存行数据的。

三、B树与B+树区别

1.B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。

B树的由于每个节点都有key和data，所以查询的时候可能不需要O(logn)的复杂度，甚至最好的情况是O(1)就可以找到数据，而B+树由于只有叶子节点保存了data，所以必须经历O(logn)复杂度才能找到数据

2.B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

根据空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。

B+树可以很好的利用局部性原理，若我们访问节点 key为 50，则 key 为 55、60、62 的节点将来也可能被访问，我们可以利用磁盘预读原理提前将这些数据读入内存，减少了磁盘 IO 的次数。

当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

由于B+树的叶子节点的数据都是使用链表连接起来的，而且他们在磁盘里是顺序存储的，所以当读到某个值的时候，磁盘预读原理就会提前把这些数据都读进内存，使得范围查询和排序都很快

3.B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。

这个很好理解，由于B-树节点内部每个 key 都带着 data 域，而B+树节点只存储 key 的副本，真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的，一次磁盘 IO 会读取若干个 block，具体和操作系统有关，那么由于磁盘 IO 数据大小是固定的，在一次 IO 中，单个元素越小，量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树，从这点来看B+树相对B-树磁盘 IO 次数少。

点评：由于B树的节点都存了key和data，而B+树只有叶子节点存data，非叶子节点都只是索引值，没有实际的数据，这就时B+树在一次IO里面，能读出的索引值更多。从而减少查询时候需要的IO次数！

四、MySQL 使用 B+ 树

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

1.存储数据最小单元

在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）他的最小单元是块，一个块的大小是4k

而对于我们的InnoDB存储引擎也有自己的最小储存单元——页（Page），一个页的大小是16K。

文件系统中一个文件大小只有1个字节，但不得不占磁盘上4KB的空间。

磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。

B+树的叶子节点就是数据页

在MySQL中InnoDB页的大小默认是16k，当然也可以通过参数设置：

mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.01 sec)

2.磁盘存取

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

3.局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

所以IO一次就是读一页的大小