浅析数据库算法与数据结构(三) B树

简介: 上一期我们谈到了数据库实现快速查找的所使用的的HASH算法,能够实现O(1)复杂的快速查找,HASH算法虽然好,但是有一个致命的缺点,就是HASH函数算出的散列值,通常是随机分布,没有顺序性。这时候我们就需要使用到B树

上一期我们谈到了数据库实现快速查找的所使用的的HASH算法,能够实现O(1)复杂的快速查找,HASH算法虽然好,但是有一个致命的缺点,就是HASH函数算出的散列值,通常是随机分布,没有顺序性。而很多时候数据库的数据是有数值含义的,需要实现诸如

SELECT * FROM CUSTOMER WHERE ORDER_AMOUT > 100

类似这样的范围查找,这样的需求,哈希算法是无法实现,那我们就需要有一类能够保持关键字段稳定排列的算法或数据结构,这时候我们就需要用到BTREE,B树

 

B树

1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:

1、根结点至少有两个子女;

2、每个非根节点所包含的关键字个数 j 满足:【m/2】 - 1 <= j <= m - 1;

3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故内部子树个数 k 满足:【m/2】 <= k <= m ;

4、所有的叶子结点都位于同一层。

image3.png

 

 

B树的查找

如图所示,B+树中含有两个头指针,一个指向整棵树的根结点,另一个指向关键字最小的叶子结点。同时所有的叶子结点依据其关键字的大小自小而大顺序链接,所有的叶子结点构成了一个 sqt 指针为头指针的链表。

 

所以,B+树可以进行两种查找运算:一种是利用 sqt 链表做顺序查找,另一种是从树的根结点开始,进行类似于二分查找的查找方式。

 

能够使用二分法进行查找,就意味着查找效率接近O(lgN)级别,可以以非常快的速度在大量的数据中进行查找,并且也满足了我们一开始想要实现的还能够进行顺序查找的操作。

 

B树在数据库中的使用

B树在数据库中的使用有

B树索引:为了加快查找速度,我们可以在数据记录的关键字段上建立B树索引,这样的索引既可以进行等值查找,也可以进行范围查找,等值查找的操作速度略逊于HASH

聚集表/索引组织表:为了能够实现数据的快速访问,很多数据库甚至将表按照住建组织成了B树的形式,这样按照主键来查询数据或者范围查找数据是非常快的,比如MySQL InnoDB引擎的表的组织形式就是B树

image33.png

目录
相关文章
|
5天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
70 29
|
5天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
59 25
|
5天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
53 23
|
30天前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
58 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
30天前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
46 12
|
30天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
42 10
|
30天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
47 2
|
23天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
23天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
121 68
|
1月前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。

热门文章

最新文章