背景
首先, 来谈谈 B 树. 为什么要使用 B 树? 我们需要明白以下两个事实:
[事实 1]
不同容量的存储器, 访问速度差异悬殊. 以磁盘和内存为例, 访问磁盘的时间大概是 ms 级的, 访问内存的时间大概是 ns 级的. 有个形象的比喻, 若一次内存访问需要 1 秒, 则一次外存访问需要 1 天. 所以, 现在的存储系统, 都是分级组织的. 最常用的数据尽可能放在更高层, 更小的存储器中, 只有在当前层找不到, 才向更低层, 更大的存储器中寻找. 这也就解释了, 当处理大规模数据的时候(指无法将数据一次性存入内存), 算法的实际运行时间, 往往取决于数据在不同存储级别之间的 IO 次数. 因此, 要想提升速度, 关键在于减少 IO.
[事实 2]
磁盘读取数据是以数据块 (block)(或者: 页, page) 为基本单位的, 位于同一数据块中的所有数据都能被一次性全部读取出来. 换句话说, 从磁盘中读 1B, 与读 1KB 几乎一样快! 因此, 想要提升速度, 应该利用外存批量访问的特点, 在一些文章中, 也称其为磁盘预读. 系统之所以这么设计, 是基于一个著名的局部性原理:
当一个数据被用到时, 其附近的数据也通常会马上被使用, 程序运行期间所需要的数据通常比较集中
B 树
假设有 10 亿条记录(1000*1000*1000), 如果使用平衡二叉搜索树(Balanced Binary Search Tree, BBST), 最坏的情况下, 查找需要 log(2, 10^9) = 30 次 I/O 操作, 且每次只能读出一个关键字(即如果这次读出来的关键字不是我要查找的, 就要再进行一次 I/O 去读取数据). 如果换成 B 树, 会是怎样的情况呢?
B 树是为了磁盘或其它辅助存储设备而设计的一种多叉平衡搜索树. 多级存储系统中使用 B 树, 可针对外部查找, 大大减少 I/O 次数. 通过 B 树, 可充分利用外存对批量访问的高效支持, 将此特点转化为优点. 每下降一层, 都以超级结点为单位(超级结点就是指一个结点内包含多个关键字), 从磁盘中读入一组关键字. 那么, 具体多大为一组呢?
一个节点存放多少数据视磁盘的数据块大小而定, 比如磁盘中 1 block 的大小有 1024KB, 假设每个关键字的大小为 4 Byte, 则可设定每一组的大小 m = 1024 KB / 4 Byte = 256. 目前, 多数数据库系统采用 m = 200~300. 假设取 m = 256, 则 B 树存储 1 亿条数据的树的高度大概是 log(256, 10^9) = 4, 也就是单次查询所需要进行的 I/O 次数不超过 4 次, 由此大大减少了 I/O 次数.
一般来说, B 树的根节点常驻于内存中, B 树的查找过程是这样的: 首先, 由于一个节点内包含多个 (比如, 是 256 个) 关键码, 所以需要先顺序 / 二分来查找, 如果找到则查找成功; 如果失败, 则根据相应的引用从磁盘中读入下一层的节点数据(这里就涉及到一次磁盘 I/O), 同样的在节点内顺序查找, 如此往复进行... 事实上, B 树查找所消耗的时间很大一部分花在了 I/O 上, 所以减少 I/O 次数是非常重要的.
B 树的定义
B 树就是平衡的多路搜索树, 所谓的 m 阶 B 树, 即 m 路平衡搜索树. 根据维基百科的定义 https://en.wikipedia.org/wiki/B-tree#Definition , 一棵 m 阶 B 树需满足以下要求:
每个结点至多含有 m 个分支节点(m>=2).
除根结点之外的每个非叶结点, 至少含有┌m/2┐个分支.
若根结点不是叶子结点, 则至少有 2 个孩子.
一个含有 k 个孩子的非叶结点包含 k-1 个关键字. (每个结点内的关键字按升序排列)
所有的叶子结点都出现在同一层. 实际上这些结点并不存在, 可以看作是外部结点.
根据节点的分支的上下限, 也可以称其为 (┌m/2┐, m) 树. 比如, 阶数 m=4 时, 这样的 B 树也可以称为 (2,4) 树.(事实上,(2,4)树是一棵比较特殊的 B 树, 它和红黑树有着特别的渊源! 后面谈及红黑树时会谈到.)
并且, 每个内部结点的关键字都作为其子树的分隔值. 比如, 某结点含有 2 个关键字(假设为 a1 和 a2), 也就是说该结点含有 3 个子树. 那么, 最左子树的关键字均小于 a1; 中间子树的关键字介于 a1~a2; 最右子树的关键字均大于 a2.
示例, 一棵 3 阶的 B 树是这个样子:
B 树的高度(了解)
假定一棵 B 树非空, 具有 n 个关键字, 高度为 h(令根结点为第 1 层), 阶数为 m, 那么该 B 树的最大高度和最小高度分别是多少?
最大高度
当树的高度最大时, 则每个结点含有的关键字数应该尽量少. 根据定义, 根结点至少有 2 个孩子(即 1 个关键字), 除根结点之外的非叶结点至少有┌m/2┐个孩子(即┌m/2┐-1 个关键字), 为了描述方便, 这里令 p = ┌m/2┐.
第 1 层 1 个结点 (含 1 个关键字)
第 2 层 2 个结点 (含 2*(p-1)个关键字)
第 3 层 2p 个结点 (含 2p*(p-1)^2 个关键字)
...
第 h 层 2p^(h-2)个结点
故总的结点个数 n
≥ 1+(p-1)*[2+2p+2p^2+...+2p^(h-2)]
≥ 2p^(h-1)-1
从而推导出 h ≤ log_p[(n+1)/2] + 1 (其中 p 为底数, p=┌m/2┐)
最小高度
当树的高度最低时, 则每个结点的关键字都至多含有 m 个孩子(即 m-1 个关键字), 则有
n ≤ (m-1)*(1 + m + m^2 +...+ m^(h-1)) = m^h - 1
从而推导出 h ≥ log_m(n+1) (其中 m 为底数)
B + 树
B + 树的定义
B + 树是 B 树的一个变体, B + 树与 B 树最大的区别在于:
叶子结点包含全部关键字以及指向相应记录的指针, 而且叶结点中的关键字按大小顺序排列, 相邻叶结点用指针连接.
非叶结点仅存储其子树的最大 (或最小) 关键字, 可以看成是索引.
一棵 3 阶的 B + 树示例:(好好体会和 B 树的区别, 两者的关键字是一样的)
问: 为什么说 B + 树比 B 树更适合实际应用中操作系统的文件索引和数据库索引?
答:
B + 树更适合外部存储. 由于内结点不存放真正的数据(只是存放其子树的最大或最小的关键字, 作为索引), 一个结点可以存储更多的关键字, 每个结点能索引的范围更大更精确, 也意味着 B + 树单次磁盘 IO 的信息量大于 B 树, I/O 的次数相对减少.
MySQL 是一种关系型数据库, 区间访问是常见的一种情况, B + 树叶结点增加的链指针, 加强了区间访问性, 可使用在区间查询的场景; 而使用 B 树则无法进行区间查找.
参考:
1)清华大学邓俊辉数据结构 - 高级搜索树
2) (数据结构可视化)
来源: https://www.cnblogs.com/kkbill/p/11381783.html