多路查找树(B树)

概念 :

回忆起AVL树

• 每一次插入或删除总是为了保持树的平衡性而旋转,增加了性能的消耗。

• 一个结点只能存储一个元素，在元素非常多时，树的高度和度非常大，使得内存存取外存次数多

所以，我们引入了一种绝对平衡且单结点可以存储多个元素的树，即为多路查找树

具体实现

• 2-3树
• 2-3-4树
• B树
• B+树

2-3树

定义

• 2-3以及之后的2-3-4树都属于特殊的B树

• 其任意节点到它所有叶子节点的深度都是相等的

• 每一个结点有2个(2结点)或者3个(3结点)

  • 一个2结点包含一个元素,两个孩子

    构成与二叉树类似,不过只存在空树或者满树(两个孩子)

  • 一个3结点包含一大一小两个元素,三个孩子

    值的比较：L<P1<M<P2<R

    同时也只能存在空树或者满树

插入

类似于二叉树，插入操作发生在叶子结点，不同的是会发生结构的连锁反应

有一下几种情况，用近python格式伪码呈现

if 插入叶子结点C是二结点树
        C成为三结点树
        return
    
if 插入叶子结点C是三结点树
	if 双亲P是二结点树
        P成为三结点树
        return
    if 双亲P是三结点树
		P拆分为两颗二结点树
        or 
        整个树的高度增加
    	return

删除

插入的逆过程

• 第一种情况：删除的叶子结点属于3结点的位置（双亲属于3结点树）

​ 直接删除，3结点变2结点

• 第二种情况：删除的叶子结点C属于2结点的位置

  分四种情况

  • 双亲2结点，有个3节点的孩子（C的兄弟）：删除C，以双亲进行旋转
  • 双亲2结点，有个2节点的孩子（C的兄弟）：删除C，以双亲的双亲进行旋转
  • 双亲3结点：删除C，双亲拆分为2个2结点树
  • 满二叉树：删除C，降低树的层数

• 第三种情况： 删除的节点非叶子结点

​ 中序遍历该结点的前驱或者后驱元素，进行补位

2-3-4树

属于23树的拓展，基本属性相同，多了一个4结点的使用。

其包含了小中大三个元素和4个孩子（或者没有孩子）

B树

B树是一种平衡的多路查找树，结点最大的孩子数目为B树的阶（order）

可以先从下面的2-3树开始理解，再看B树的内容

一个m阶的B树具有如下属性

• 如果根结点不是叶结点。则至少有两颗树

• 每个非根的分支结点都有k-1个元素和K个孩子,每一个叶子结点n都有k-1个元素

  其中 (m/2) <= k <= m 其中 / 取整

• 所有叶子结点都位于同一层次

• 与其他平衡二叉树类似，B-树查找、插入和删除操作的时间复杂度为O(logn) 量级

  其中数据排列具有以下特征

• 所有分支结点包含以下数据信息(n,A₀,K₁,A₁,K₂,A₂……K_n,A_n)

• n为关键字个数 (m/2)-1 <= n <= m-1

• 所有的A、K同下标正相关

• ​ A_n-1 <= K_n <= A_n

  

结构优势

减少内存与外存的的数据交换次数(例如减少硬盘读写)

同时数据内容过于庞大不能够一次性读进内存

可以说是专门为内外存数据交互准备的

• 将B树阶数同硬盘存储页面大小相匹配

  例如: 1001阶、高度2的树，可以存储10亿个关键字

• 将根结点永久保存在内存中

• 查找某个关键字至多需要2次硬盘读写

对于查找n个关键字的m阶B树，查找一个数据，仅仅支持随机查找

B+树

b树虽然利于内外村交互，但是再查找过程中，对于硬盘的遍历还是存在缺陷的。

再中序遍历中，尤其是再孩子都处于不同硬盘页面时，会进行多次的页面转换、重复遍历（尤其是对结点也可以说是双亲的元素）

为了解决多次遍历的问题，引入了B+树

差异

对比b树

• 有n棵树的结点有n个关键字
• 所有叶子结点包含全部关键字的信息，以及指向这些关键字记录的指针，叶子结点本身依据关键字大小从小到大顺序链接
• 所有的分支结点可以看成索引，记录了叶子子女的最大（或者最小）元素

优势

• 可以进行随机查找（方式同B树一样，从根结点开始），但是在非子树上的只能是索引，只会找到叶子结点才会停止
• 可以进行顺序查找，直接从最左叶子结点开始，适合带有范围的查找

增删

同B树类似，不过全体在叶子结点进行