b-树#

定义#

• 结点的孩子个数的最大值称为B树的阶
• m阶b树内部节点孩子个数最大$m$,关键字数量最大$m-1$
• 若根结点不是终端结点，则至少有两棵子树，和一个关键字
• 除根节点外的内部节点至少有$\lceil{m/2}\rceil$个子树，$\lceil{m/2}\rceil-1$个关键字
• 外部节点都是失败节点所有的叶结点都出现在同一层次上

计算#

• 当关键字数量固定，树的高度的范围是（不包括外部节点）
  • 最矮$\log_{m}{n+1}$
  • 最高$log_{\lceil m/2 \rceil}{(n+1)/2}+1$
• 当树高固定，关键字数量的范围是
  • 最多$m^h -1$
  • 最少$2\lceil m/2 \rceil^{h-1}-1$

插入#

• 没有破坏规则 结束
• 如果个数超过上限，在$\lceil m/2 \rceil$个关键词处分裂，该关键词并入父亲分裂的两部分成为父亲的两个新儿子，如果父亲因并入新关键字导致个数也超过了上限则也进行分裂，迭代地进行这个过程直到规则没被破坏或者传到根导致树高加1

删除#

• 如果删除内部节点则找直接前驱或者后继代替位置，那么就转换成了删除终端节点关键字的问题
• 如果删除完终端节点关键字后关键字数量没有小于最小值 结束
• 如果删除完终端节点关键词过少不足以维持一个节点时
  • 兄弟够借 左兄弟或者右兄弟够借一个节点时，从兄弟中借一个变成父关键字，原关键字拉下来补充
  • 不够借 与兄弟节点和被夹在中间的关键字合成一个终端节点，此时有可能造成父节点关键字过少不足以维持一个节点，此时要迭代地自底向上调整直到不破坏规则或者到根节点

b+树#

• 内部节点是对叶子节点的索引
• 叶子节点链接成链表支持随机访问（即按关键字访问）与顺序访问，区别与b树仅支持随机访问

红黑树#

定义#

• 等价于一颗2-3-4b树
• 每一个节点要么是黑的要么是红的，红色节点是父亲黑色节点的卫星节点，黑色节点与隶属的红色节点对应b树的一个内部节点
• 根是黑的 对应b树的根节点
• 叶子节点是失败节点是黑的 对应b树的失败节点
• 不存在两个相邻的红色节点 对应b树的关键字数量有限制
• 根到叶子的黑高相同 对应外部节点都是失败节点所有的叶结点都出现在同一层次上

插入#

• 树为空则新节点是根，染为黑色
• 新节点非根，染为红色
  • 父亲是黑色 结束
  • 父亲是红色 那么爷爷一定是黑色 叔叔要么是黑色要么是红色
    • 如果叔叔是黑色，那么该节点与父亲与爷爷构成一个b树的3关键字节点，并没有破坏b树的规则，只是要调整节点与父亲与爷爷的关系
      • 对于LL与RR的情况 只要让父亲成为恒星节点，我与爷爷成为父亲的卫星节点即可
      • 对于LR与RL 我调整为恒星节点，爸爸与爷爷成为卫星节点
    • 如果叔叔是红色，那么这四个节点构成了一个4关键字的b树节点，破坏了b树的规则，所以4关键字节点要分家，具体做法是让爷爷变成红色节点，爸爸与叔叔成为黑色，爷爷成为了上面一层黑色节点的卫星节点，此时可能导致对应的黑色节点构成的b树节点关键字数量超过上限，所以要递归地做同样的操作直到规则没被破坏或者上移到根，此时把红色节点染成黑色

删除#

…