B树、B+树速记

B树

  • 每个节点最多有m-1个关键字(可以存有的键值对)。
  • 根节点最少可以只有1个关键字。
  • 非根节点至少有m/2个关键字。
  • 每个节点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。
  • 所有叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同。
  • 每个节点都存有索引和数据,也就是对应的key和value。
  • 所以,根节点的关键字数量范围:1 <= k <= m-1,非根节点的关键字数量范围:m/2 <= k <= m-1
    插入【B树、B+树速记】直接插入到叶节点的对应位置,如果数量超过m则分裂,将中间k上升到父结点中
删除 直接删除,如果删除后数量少于m/2(m/2-1),则从兄弟节点中借k(兄弟节点k上升到父节点,父节点中一个k下降到当前节点中),如果兄弟节点中没有能借的k(数量不多于m/2),则与兄弟节点合并(此时会从父节点中借一个k)。
B+树 B+树其实和B树是非常相似的,我们首先看看相同点。
相同点:
  • 根节点至少一个元素
  • 非根节点元素范围:m/2 <= k <= m-1
不同点:
  • B+树有两种类型的节点:内部结点(也称索引结点)和叶子结点。内部节点就是非叶子节点,内部节点不存储数据,只存储索引,数据都存储在叶子节点。
  • 内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
  • 每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接。
  • 父节点存有右孩子的第一个元素的索引。
B树和B+树
  • 单一节点存储的元素更多,使得查询的IO次数更少,所以也就使得它更适合做为数据库MySQL的底层数据结构了。
  • 所有的查询都要查找到叶子节点,查询性能是稳定的,而B树,每个节点都可以查找到数据,所以不稳定。
  • 所有的叶子节点形成了一个有序链表,更加便于查找。

    推荐阅读