bplustree

B+树特点

• 每个节点中子节点的个数不超过m，也不能小于m/2
• 根节点的子节点个数可以不超过m/2
• m叉树只存储索引，并不真正存储数据，这个类似于跳表
• 通过链表将叶子节点串联在一起，这样可以方便查找
• 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中

B树和B+树的区别

• B+树中的节点不存储数据，只是索引，而B树中的节点存储数据
• B树的叶子节点并不需要链表来串联

B+树 - 插入部分

• 1). 若为空树，创建一个叶子节点，然后将记录插入其中，此时这个叶子也是根节点，插入操作结束
• 2). 针对叶子类型节点
  • 更具key值找到叶子节点，向这个叶子节点插入记录
  • 插入后，若当前节点key的个数小于等于 m - 1,则插入结束
  • 否则将这个叶子节点分裂成左右两个叶子节点，左叶子节点包含前 m / 2个记录，右节点包含剩下的记录，将第 m / 2 + 1个记录的key进位到父节点中(父节点一定是索引类型节点)，进位到父节点的key左孩子指针向左节点，右孩子指向右节点
  • 将当前节点的指针指向父节点，然后执行第3步
• 3). 针对索引类型
  • 若当前节点key的个数小于等于 m - 1, 则插入结束
  • 否则，将这个索引类型节点分裂成两个索引节点，左索引节点包含前(m - 1) / 2个key，右节点包含 m - (m - 1) / 2 个key，将第 m / 2 个key进位到父节点，进位到父节点的key左孩子指向左节点，进位到父节点的key右孩子指向右节点
  • 将当前节点的指针指向父节点，重复第3步

B+树 - 删除部分

• 如果叶子节点中没有相应的key，则删除失败
• 否则执行下面的步骤
  • 1). 删除叶子节点中对应的key。
    • 删除后若节点的key个数大于等于ceil(m - 1) / 2 - 1， 则删除结束
    • 否则执行第2步
  • 2). 若兄弟节点key有富余(大于 ceil(m - 1) / 2 - 1)
    • 向兄弟节点借一个记录，同时用借到的key替换父节点(指当前节点和兄弟节点共同的父节点)中的key，删除结束
    • 否则执行第3步
  • 3). 若兄弟节点中没有富余的key
    • 则当前节点和兄弟节点合并成一个新的叶子节点，并删除父节点中的key(父节点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子节点)
    • 将当前节点指向父节点(必为索引点)，执行第4步
  • 4). 若索引节点的key的个数大于等于ceil(m - 1) / 2 - 1
    • 则删除操作结束
    • 否则执行第5步
  • 5). 若兄弟节点有富余
    • 父节点key下移，兄弟节点key上移，删除结束
    • 否则执行第6步
  • 6). 当前节点和兄弟节点及父节点下移合并成一个新的节点
    • 将当前节点指向父节点，重复第4步

参考资料

• B+树怎么在磁盘存储？
• B+树总结
• B树和B+树的插入、删除图文详解
• B+树在磁盘存储中的应用
• Mysql索引机制(B+Tree)