简介
平衡多路查找树(B-Tree) 演变自 平衡二叉树，是为磁盘等外部存储设备设计的一种平衡查找树。
B-Tree 、B树指的都是同一个数据结构
磁盘基础
在计算机中
-
磁盘存储数据最小单元是扇区，一个扇区的大小是 512 字节
-
而文件系统（例如 XFS/EXT4）他的最小单元是块，一个块的大小是 4k
-
InnoDB 存储引擎的最小储存单元是页（Page），一个页的大小默认是 16K
磁盘扇区、文件系统、InnoDB 存储引擎都有各自的最小存储单元
InnoDB 存储引擎中，可通过参数 innodb_page_size 可以将页的大小设置为4K、8K、16K。
# 在MySQL下查看页的大小
show variables like 'innodb_page_size'
InnoDB 中，数据的读写都是以页为单位的，如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。
特性
B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。
Ceil()函数用于向上取整，例如Ceil(1.2)=2
一棵m阶的B-Tree有如下特性：
- 每个节点最多有m个孩子。
- 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。
- 若根节点不是叶子节点，则至少有2个孩子
- 所有叶子节点都在同一层，且不包含其它关键字信息
- 每个非终端节点包含n个关键字，关键字升序排序
- 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
存储结构
B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：
每个节点占用一个盘块的磁盘空间
一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。
两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。
以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。
模拟查找关键字29的过程：
- 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
- 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
- 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
- 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
- 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
- 在磁盘块8中的关键字列表中找到关键字29。
分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。
B-Tree相对于AVLTree缩短了树的高度，从而提高了查询效率。
不足
在B-Tree结构中每个节点不仅存储数据的key值，还存储数据的data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。
为了解决这个问题，人们又发明了 B+Tree
