前面已经介绍了二叉查找树，2-3树以及实现了红黑树。2-3数中，一个结点最对有两个key，它的实现红黑树中使用的对链接染色的方式去表达这两个key。本节我们继续介绍一种数据结构B树，这种数据结构中，一个结点允许多于两个key的存在。

4.12.1、B-树(BTree)

B树是一种树状数据结构，它能存储数据，对其进行排序并允许以O(logN)的时间复杂度进行查找，顺序读取、插入和删除等操作

4.12.1.1、BTree的特征

B树中允许一个结点中包含多个key，可以是3、4、5…、n个。现在我们选择一个参数N，来构造一个B树，可以把它称作为M阶的B树，那么该树具有如下特点：

• 每个结点最多有M-1个key，并且以升序排列
• 每个结点最多能有M个子结点
• 根结点至少有两个子结点

在实际应用中B树的阶数一般都比较大（通常大于100），所以，即使存储大量的数据，B树的高度任然比较小，这样在某种应用场景下，就可以体现出它的优势。

4.12.1.2、BTree存储数据

若参数M为5，那么每个结点最多包含4个键值对，这里以5阶B树为例，说明下BTree的数据存储：

如果插入一个值后，如果当前结点超过了4个数，那么就把中间的数向上提升，然后当前结点进行分裂成两个结点。如果提升后数到父结点后也大于了4个，那么依次网上进行提升即可。

4.12.1.3、BTree在磁盘文件中的应用

计算机操作磁盘上的文件就是通过文件系统进行操作了，在文件系统中就使用了B树这种数据结构。

• 磁盘：磁盘能够保存大量的数据，从GB一直到TB级，但是它的读取数据比较慢，因为涉及到机器操作，读取速度为毫秒级。
  

磁盘右盘片构成，每个盘片有两个面，又称为盘面。盘片中央有一个可以旋转的主轴，使得盘片以固定的旋转速率旋转，通常是5400rpm或7200rpm，一个磁盘中包含了多个这样的盘片并封装在一个封闭的容器中。盘片的每个表面是由一组称为磁道同心圆组成的，每个磁道被划分成了一组扇区，每个扇区包含相等数量的数据位，通常是512个字节，扇区之间由一些间隙隔开，这些间隙中间不存储数据。

• 磁盘IO
  

磁盘用磁头来读取存储在盘片表面的位，而磁头连接到一个移动臂上，移动臂沿着盘片半径前后移动，可以将磁头定位到任何磁道上，这个称之为寻道操作。一旦定位到磁盘后，盘片转动，磁道上的每个位经过磁头是，读写磁头就可以感知到该位的值，也可以修改值。对磁盘的访问时间可以分为：寻道时间，旋转实现和传送时间。

由于存储介质的特性，磁盘本身存取就比主存满很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被调用到时，其附近的数据通常会马上被使用。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此预读可以提高I/O效率。

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

文件系统的设计者利用了磁盘的预读原理，将一个结点的大小设置为等于一页（1024个字节或其整数倍），这样每个结点只需要一次I/O就可以完全载入。那么3层的B树可以容纳102410241024个数据，差不多10亿个，如果换成二叉查找树，则需要30层。假如操作系统一次读取一个字节，并且根结点保留在内存中，那么BTree在10亿个数据中查找目标值，只需要小于3次硬盘读取就可以找到目标值，但是红黑树需要小于30次，因此B树极度提高了IO的操作效率。

4.12.2、B+树(B+Tree)

B+树是对B树的一种变形树，它和B树的差异在于：

• 非叶结点仅具有索引作用，也就是说，非叶节点值存储key，不存储value
• 树的所有也结点构成一个有序的链表，可以按照key排序的次序遍历全部数据

4.12.2.1、B+树和B树的对比

B+树的优点：

• B+树的非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key
• B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历

B树的优点：

• 由于B树的每个结点都包含了key和value，因此我们根据key查找value是，只需要找到key的位置，就能找到value，但是B+树只有叶子结点存储数据，索引每一次查找都必须一次次，一直找到树的最大深度处，也就是叶子结点的深度，才能找到value

4.12.2.2、B+树在数据库中的应用

在数据库的操作中，查询操作是最频繁的操作，因此在设计数据库时，就需要考虑到查询效率问题，在很多数据库中，都会用到B+树来提高查询效率。

在操作数据库时，我们为了提高查询效率，可以基于某张表的某个字段建立索引，就可以提高查询效率，那其实这个索引就是B+树数据结构的实现。

• 未建立主键索引的查询
  

执行select * from user where id = 18;需要从第一条数据开始，一直查询到第六条，发现id=18，此时才能查询出目标结果，共需要比较6次。

• 建立主键索引查询
  

• 区间查询
  执行select * from user where id >=12 and id <=18，如果有了索引，由于B+树的叶子结点形成了一个有序链表，所以我们只需要找到id为12的叶子结点，按照遍历链表的方式顺序往后查即可，效率非常高。