btree学习笔记

简介

btree：balance tree，平衡多叉树，类比avl：平衡二叉树，都是有平衡的属性 (多个子树高度一致)，只不过是二叉和多叉的区别。

使用场景

文件系统如extfs、jffs，sql，磁盘上的索引查找场景。多叉树的层级相比二叉树会更低，磁盘查找中，树的每一层访问相当于一次IO操作，多叉树会减少IO操作。

• 二叉树磁盘访问

如下实例7个索引，3层，3次IO操作。

• 多叉树

一个磁盘块可以保存多个索引，7个节点，2层，只有2次IO操作，多叉树有更少的IO操作。

btree中的概念

• 多叉树顺序：从左往右数字增长。

• btree的节点

一个节点中可以有：指针、数据 (key、value)

1）指针：指向子节点。

2）数据中有key 值 和 保存的具体数据。

叶子节点：只有数据，没有孩子节点，即指针为空。

• 阶数

一个节点最多有多少个孩子节点。(指针个数)

• 指针和数据的个数：

1）数据比指针少1个

2）根节点最少1个数据

3）对于m阶btree，非根节点最少m/2 -1 个数据。

一个磁盘块一般保存一个节点。（磁盘索引特点，非btree的特点）

如何保证平衡

• 平衡的概念：访问每个叶子节点的层级要尽可能一致，防止抖动太多。

• 平衡的定义：(类比)

avl：左右子树的高度差1;

rbtree：黑高；

btree: 所有叶子节点在同一层。

• 执行平衡的动作：

avl：左右旋转。

btree：分裂。

分裂操作

分裂 + 进位(上浮)

从节点中心分裂，分裂出来的节点 插入到父节点 (进位)。 上浮到根节点后层级变高。

插入 和 删除的操作：

参见：B树和B+树的插入、删除图文详解 - nullzx - 博客园 (cnblogs.com)

B+ tree

非叶子节点的数据中只有key，而没有value，这样一个磁盘块中可以保存更多的指针和key，分叉可以更多。

参见：BTree和B+Tree详解_b+brtt的结构图_菜鸟笔记的博客-CSDN博客

参考资料

BTree和B+Tree详解_b+brtt的结构图_菜鸟笔记的博客-CSDN博客

B树和B+树的插入、删除图文详解 - nullzx - 博客园 (cnblogs.com)