最近在做CMU的15445的数据库课程, 需要复习一些高级的数据结构. 记录了一些学习笔记.
B树(B-Tree)
B树实际上是从二叉平衡树衍生而来, B树的B是 Balanced Tree 的意思, 并不是二叉树的意思.
与传统的二叉搜索树不同, B树的特征是它们可以存储在单个节点中的大量键值对, 这就是为什么它们也被称为“大键”树的原因. B树中的每个节点都可以包含多个键, 这使树具有较大的分支因子, 从而减小树的深度. 较小的深度导致磁盘I/O较少, 从而可以更快的进行搜索和插入操作. B树特别适合缓慢, 大量的数据访问(例如硬盘驱动器，闪存和CD-ROM)的存储系统.
B树的时间复杂度
B树的搜索, 插入, 与删除的时间复杂度均为 \(O(log\ n)\).
B树的性质
- 所有的叶子节点都在同一层
- 限制B树大小结构的元素是最小度 \(t\), \(t\) 的值取决于磁盘块的大小. 例如, 我们下图中的磁盘块的大小为2.
- 除了根节点之外, 每一个节点至少包含 \(t-1\) 个Key, 根节点至少有一个 Key.
- 所有的节点, 包括根节点, 至多有 \(2t -1\) 个Keys.
- 一个节点的孩子的个数, 等于这个节点的Keys的个数加一
- 一个节点中, 所有的Keys是按照升序排列的. \(Key_1\) 和 \(Key_2\) 之间的所有孩子节点包含 \((Key_1, Key_2)\) 范围内的 Keys.
- B 树的插入只发生在叶子节点.
除了我上述使用使用最小度来限制B树的结构, 另一个B树的属性是Order \(m\). 也就是我们常说的 \(m\) 阶. 一个 \(m\) 阶的B树每个节点最多有 \(m\) 个孩子. 一棵 \(m\) 阶的B-Tree有如下特性：
- 每个节点最多有 \(m\) 个孩子.
- 除了根节点和叶子节点外, 其它每个节点至少有 \(\lceil \frac{m}{2} \rceil\) 个孩子.
- 若根节点不是叶子节点, 则至少有2个孩子.
- 所有叶子节点都在同一层, 且不包含其它关键字信息.
- 每个非终端节点包含 \(n\) 个关键字信息
- 关键字的个数 \(n\) 满足：\(\lceil \frac{m}{2} \rceil-1 <= n <= m-1 \)
注意这是从两个不同的属性来定义一颗 B树的, 满足 \(t = \lceil \frac{m}{2} \rceil\). 但是 \(m=2t\)不一定成立, 所以如果给出了一棵树的 \(t\) 和 \(m\), 我们需要同时满足.
标签：,lceil,Keys,Tree,叶子,Key,节点 From： https://www.cnblogs.com/wevolf/p/18305721