B+树与B-树
2024-02-20 16:42:22
前面已经介绍过B-树，接下来，我们主要介绍一下B+树。
1、B+树的概念
B+树是应文件系统所需而生的一种B-树和变形树。一棵m阶B+树和m阶的B-树的差异在于：
（1）有n棵子树的结点中含有n个关键字。
（2）所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身关键字的大小自小而大顺序链接。
（3）所有的非终端节点可以看成是索引部分，结点 中仅含有其子树（根结点）中的最大（小）关键字。
B+树通常有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点。因些，对于B+树进行查找两种运算：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。
2、B+树的查找
跟B树的查找类似，但是也有不同。由于跟记录有关的信息存放在叶结点中，查找时若在上层已找到待查的关键码，并不停止，而是继续沿指针向下一直查到叶结点层的关键码。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。此外，B+树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。上面两种方式结合起来，使得B+树非常适合范围检索。
3、B+树的插入
B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行，如果叶结点中的关键码个数超过m，就必须分裂成关键码数目大致相同的两个结点，并保证上层结点中有这两个结点的最大关键码。
4、B+树的删除
B+树中的关键码在叶结点层删除后，其在上层的复本可以保留，作为一个"分解关键码"存在，如果因为删除而造成结点中关键码数小于ceil(m/2)，其处理过程与B-树的处理一样。
最新文章
- JS多异步之间的协作方案
- Entity Framework Code First （七）空间数据类型 Spatial Data Types
- Git学习笔记 git revert
- dict内部方法
- Spring中配置文件applicationContext.xml配置详解
- web前端开发（2）
- Win7远程登录Ubuntu14.04
- OPENQUERY
- 加载为应用程序池‘DefaultAppPool'提供服务的进程失败，应用程序池被禁用【解决方法】
- vbox要手动mount才能挂载windows的共享文件夹（好用，不用安装samba了）
- hdu3555（数位dp）
- installshield学习笔记
- pycharm 序列号/行号 的宽度太宽了如何调整
- __name__ __main__ 作用
- AOP切面实现原理以及多个切面切同一个地方时的优先级讲解
- 终于解决了用JAVA写窗口程序在不同的windows界面下的显示保持一致。
- Netty原理分析
- mongoDb CPU利用率100%的分析和解决
- Android开发之--常用颜色值
- linux下面安装maven