python实现B/B+树

news/2024/5/30 16:44:49/文章来源:https://blog.csdn.net/liulanba/article/details/136600499

python实现–顺序查找
python实现–折半查找
python实现–分块查找
python实现B/B+树

B树和B+树都是一种多路搜索树,用于对大量数据进行排序和查找。它们在数据库系统中被广泛应用,特别是用于构建索引结构。

B树(B-Tree)

B树,又称多路平衡查找树,B树中所有结点的孩子结点数的最大值称为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:
1)树中每个结点至多有m棵子树(即至多含有m-1个关键字)。
2)若根结点不是终端结点,则至少有两棵子树。
3)除根结点外的所有非叶结点至少有[m/2]棵子树(即至少含有[m/2]-1个关键字)
4)所有叶子节点都在同一层。
5)每个节点中的关键字按照升序排列。

B树的优点包括:
减少访问磁盘的次数:B树的每个节点可以存储更多的关键字,因此树的高度相对较低,从而减少了访问磁盘的次数。
适应不同的数据规模:B树可以根据数据规模动态调整节点大小,适应不同的数据规模。

B+树(B-Plus Tree)

B+树是在B树的基础上进行改进的一种树结构,它与B树的区别在于:

所有关键字都出现在叶子节点中,而非内部节点。
内部节点仅用于索引,不存储数据,叶子节点包含了所有数据项。

B+树的特点包括:
叶子节点形成了有序链表,可以支持范围查找和范围查询。
内部节点不存储数据,只存储索引,因此可以存储更多的关键字。
由于关键字只出现在叶子节点中,因此B+树的查找性能更加稳定。

B树和B+树的比较:
查询性能:B+树的查询性能通常优于B树,因为B+树的叶子节点形成了有序链表,可以支持范围查询操作。
范围查询:B+树更适合范围查询操作,而B树的查询效率相对较低。
数据存储:B+树的数据仅存储在叶子节点中,而B树的数据可能分布在所有节点中,因此B+树更适合磁盘存储,减少了节点的访问次数。
内部节点:B树的内部节点可能包含数据,而B+树的内部节点仅用于索引,不存储数据。

总结:
B树和B+树都是常用的多路搜索树结构,在数据库系统中广泛应用。它们都具有平衡性和多路性的特点,但在一些方面有所不同,因此在实际应用中需要根据具体需求选择合适的树结构。

算法实现

B树的实现思路
定义B树节点类:B树的节点需要存储关键字和子节点的信息。我们可以定义一个节点类,其中包含关键字列表和子节点列表。
插入操作:B树的插入操作需要保持树的平衡性。当插入一个关键字时,需要根据B树的特性将关键字插入到合适的位置,并可能进行节点的分裂和合并操作,以维持B树的平衡性。
删除操作:B树的删除操作也需要保持树的平衡性。当删除一个关键字时,需要根据B树的特性对节点进行合并和移动操作,以维持B树的平衡性。

class BTreeNode:def __init__(self, leaf=False):self.keys = []self.children = []self.leaf = leafclass BTree:def __init__(self, t):self.root = BTreeNode()self.t = tdef insert(self, key):if len(self.root.keys) == (2 * self.t) - 1:new_root = BTreeNode()new_root.children.append(self.root)self.split_child(new_root, 0)self.root = new_rootself._insert(self.root, key)def _insert(self, node, key):if node.leaf:i = 0while i < len(node.keys) and key > node.keys[i]:i += 1node.keys.insert(i, key)else:i = 0while i < len(node.keys) and key > node.keys[i]:i += 1if len(node.children[i].keys) == (2 * self.t) - 1:self.split_child(node, i)if key > node.keys[i]:i += 1self._insert(node.children[i], key)def split_child(self, parent, index):t = self.tchild = parent.children[index]new_child = BTreeNode(leaf=child.leaf)parent.keys.insert(index, child.keys[t - 1])parent.children.insert(index + 1, new_child)new_child.keys = child.keys[t:]child.keys = child.keys[:t - 1]if not child.leaf:new_child.children = child.children[t:]child.children = child.children[:t]def __str__(self):return self.print_tree(self.root)def print_tree(self, node, level=0):ret = ""if node:ret += self.print_tree(node.children[-1], level + 1)for i in range(len(node.keys) - 1, -1, -1):ret += "\n" + ("    " * level) + str(node.keys[i])ret += self.print_tree(node.children[i], level + 1)return ret# 测试
btree = BTree(2)
keys = [3, 7, 1, 4, 9, 2, 6, 5, 8]
for key in keys:btree.insert(key)
print(btree)

B树实现讲解:
BTreeNode类:定义了B树的节点类,包含关键字列表 keys 和子节点列表 children,以及一个标志位 leaf 表示是否为叶子节点。
BTree类:定义了B树类,包含了B树的插入操作 insert、节点分裂操作 split_child,以及辅助方法 _insert 和打印方法 print_tree。
insert方法:首先判断根节点是否已满,如果是则分裂根节点;然后调用辅助方法 _insert 插入关键字。
_insert方法:递归地在合适的位置插入关键字,并在需要时进行节点分裂。
split_child方法:分裂节点,将中间的关键字提升到父节点,并将节点分裂成两个节点。

B+树的实现思路
定义B+树节点类:B+树的节点需要存储索引信息和叶子节点指针。我们可以定义一个节点类,其中包含关键字列表、子节点列表和叶子节点指针。
插入操作:B+树的插入操作与B树类似,但是需要额外处理叶子节点之间的连接关系,以保持叶子节点形成的有序链表。
删除操作:B+树的删除操作也与B树类似,但是同样需要额外处理叶子节点之间的连接关系。

class BPlusTreeNode:def __init__(self, leaf=False):self.keys = []self.children = []self.next_leaf = None  # 指向下一个叶子节点self.leaf = leafclass BPlusTree:def __init__(self, t):self.root = BPlusTreeNode(leaf=True)self.t = tdef insert(self, key):if len(self.root.keys) == (2 * self.t) - 1:new_root = BPlusTreeNode()new_root.children.append(self.root)self.split_child(new_root, 0)self.root = new_rootself._insert(self.root, key)def _insert(self, node, key):if node.leaf:i = 0while i < len(node.keys) and key > node.keys[i]:i += 1node.keys.insert(i, key)else:i = 0while i < len(node.keys) and key > node.keys[i]:i += 1if len(node.children[i].keys) == (2 * self.t) - 1:self.split_child(node, i)if key > node.keys[i]:i += 1self._insert(node.children[i], key)def split_child(self, parent, index):t = self.tchild = parent.children[index]new_child = BPlusTreeNode(leaf=child.leaf)parent.keys.insert(index, child.keys[t - 1])parent.children.insert(index + 1, new_child)new_child.keys = child.keys[t:]child.keys = child.keys[:t - 1]if not child.leaf:new_child.children = child.children[t:]child.children = child.children[:t]def __str__(self):return self.print_tree(self.root)def print_tree(self, node, level=0):ret = ""if node:ret += self.print_tree(node.children[0], level + 1)for i in range(len(node.keys)):ret += "\n" + ("    " * level) + str(node.keys[i])ret += self.print_tree(node.children[i + 1], level + 1)return ret# 测试
bplustree = BPlusTree(2)
keys = [3, 7, 1, 4, 9, 2, 6, 5, 8]
for key in keys:bplustree.insert(key)
print(bplustree)

B+树实现讲解:
BPlusTreeNode类:定义了B+树的节点类,与B树节点类相似,但是多了一个指向下一个叶子节点的指针 next_leaf。
BPlusTree类:定义了B+树类,与B树类相似,但是插入和分裂操作需要额外处理叶子节点之间的连接关系。
insert方法:与B树的插入操作类似,但是需要在插入关键字时维护叶子节点之间的连接关系。
split_child方法:与B树的节点分裂操作类似,但是需要额外维护叶子节点之间的连接关系。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1006903.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

压缩json字符串

GZIPOutputStream 需要关闭&#xff0c;而 ByteArrayOutputStream 不需要关闭。具体原因如下&#xff1a; GZIPOutputStream&#xff1a;GZIPOutputStream是一种过滤流&#xff0c;它提供了将数据压缩为GZIP格式的功能。当使用此类的实例写入数据时&#xff0c;它会对数据进行压…

《OWASP TOP10漏洞》

0x01 弱口令 产生原因 与个人习惯和安全意识相关&#xff0c;为了避免忘记密码&#xff0c;使用一个非常容易记住 的密码&#xff0c;或者是直接采用系统的默认密码等。 危害 通过弱口令&#xff0c;攻击者可以进入后台修改资料&#xff0c;进入金融系统盗取钱财&#xff0…

python的函数与类的定义

目录 1.函数 1.函数的定义 2.输入参数与输出参数的类型 3.输入和输出多个参数 1.普通参数 2.含有任意数量的参数 3.关键字参数 4.普通参数与多个参数的结合 2.类 1.类的定义 2.类的实例化 3.继承 1.函数 1.函数的定义 def 函数名(输入参数): 文档字符串 函数体 …

探索并发编程:深入理解 CyclicBarrier 的原理

文章目录 前言一、CyclicBarrier是什么&#xff1f;二、CyclicBarrier工作原理三、CyclicBarrier常用重要的方法四、代码实战讲解五、CyclicBarrier对比CountDownLatch总结 前言 在多线程编程中&#xff0c;同步是一项关键的任务&#xff0c;尤其是当涉及到多个线程需要在某个…

【Web】浅聊Java反序列化之C3P0——JNDI注入利用

目录 简介 原理分析 EXP 前文&#xff1a;【Web】浅聊Java反序列化之C3P0——URLClassLoader利用 【Web】浅聊Java反序列化之C3P0——不出网Hex字节码加载利用 简介 出网的情况下&#xff0c;这个C3P0的Gadget可以和fastjson&#xff0c;Snake YAML , JYAML,Yamlbeans , …

HEU_KMS激活工具(激活windows系统和office)

功能 激活windows系统和office&#xff0c;龙年限定版 步骤 自主选择激活内容和激活方式&#xff0c;快捷方便&#xff0c;注意使用工具的时候退出杀毒软件和防火墙 资源获取 链接&#xff1a;百度网盘 请输入提取码 提取码&#xff1a;q7qy

MySQL用法---MySQL Workbench创建数据库和表

1. 连接数据库 打开软件&#xff0c;点击左下角卡片&#xff0c;输入设置的数据库密码&#xff0c;勾选单选框 2. 了解主页面的组成部分 3. 创建数据库 先点击工具栏的创建按钮 再输入数据库名称 点击 Apply 创建 4. 创建数据表 展开数据库&#xff0c;在Tables上右键&…

下载无水印抖音视频

在抖音看到某些视频想下载&#xff0c;却出现无法保存在本地【显示"作品暂时无法保存,链接已复制"】。或者下载的视频有水印。 而某些微信小程序下载可能需要付费或者有水印。其实我们可以直接使用电脑浏览器直接下载。 举个例子: 这是来自王道官方账号的一条视频链…

如何利用AWS CloudFront 自定义设置SSL

Amazon CloudFront 提供三种选项&#xff0c;可以加速整个网站并从 CloudFront 的边缘站点通过安全的 HTTPS 方式交付内容。除能够安全地从边缘站点交付内容外&#xff0c;您还可以配置 CDN 来使用针对源提取的 HTTPS 连接&#xff0c;这样您的数据就会实现从源到最终用户的端到…

数据结构从入门到精通——堆

堆 前言一、二叉树的顺序结构及实现 (堆&#xff09;1.1二叉树的顺序结构1.2堆的概念及结构 二、堆的练习题答案 三、堆的实现3.1堆向下调整算法3.2堆的创建3.3建堆时间复杂度3.4堆的插入3.5堆的删除3.6堆的代码实现 四、堆的具体实现代码Heap.hHeap.cTest.c堆的初始化堆的销毁…

网络学习:9个计算机的“网络层”知识点

目录 一、IP 地址 1.1 分类表示法&#xff1a; 1.1.1 分类表示地址的其他说明 1.2 无分类编址 CIDR 二、IP 数据报文格式 Q: IP 报文里有什么&#xff1f;可以不按顺序或者字节来讲一讲 三、 路由概念 3.1 路由表 3.2 路由网络匹配 3.3 ARP 解析 3.4 RARP 逆地址解析…

Unity之PUN实现多人联机射击游戏的优化

目录 &#x1f3ae;一、 跳跃&#xff0c;加速跑 &#x1f3ae;二、玩家自定义输入昵称 &#x1f345;2.1 给昵称赋值 &#x1f345;2.2 实现 &#x1f3ae;三、玩家昵称同步到房间列表 &#x1f345;3.1 获取全部玩家 &#x1f345;3.2 自定义Player中的字段 &#…

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:Progress)

进度条组件&#xff0c;用于显示内容加载或操作处理等进度。 说明&#xff1a; 该组件从API version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口 Progress(options: ProgressOptions<Type>) 创建进度组件&a…

SpringBoot(接受参数相关注解)

文章目录 1.基本介绍2.PathVariable 路径参数获取信息1.代码实例1.index.html2.ParameterController.java3.测试 2.细节说明 3.RequestHeader 请求头获取信息1.代码实例1.index.html2.ParameterController.java3.测试 2.细节说明 4.RequestParameter 请求获取参数信息1.代码实例…

网络基础 - 预备知识(协议、网络协议、网络传输流程、地址管理)

文章目录 1. 认识 协议2. 了解 网络协议2.1 引入 协议分层2.2 OSI 七层模型 与 TCP/IP 四层模型 3. 网络传输 流程&#xff01;&#xff01;&#xff01;3.1 网络传输流程图3.2 关于报头3.3 实例解释 传输过程&#xff08;封装与解包&#xff09; 4. 网络中的地址管理4.1 认识 …

Qt中使用SDL出现error: undefined reference to `qMain(int, char**)‘

在Qt中使用SDL可能会出现下面错误error: undefined reference to qMain(int, char**) 这是因为我们在头文件中包含了SDL.h&#xff0c;这里面将main进行了替换&#xff0c;想要调用SDL_main 我们main.cpp中取消这个宏定义即可 #undef main

基于Java的天然气工程业务管理系统(Vue.js+SpringBoot)

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、使用角色3.1 施工人员3.2 管理员 四、数据库设计4.1 用户表4.2 分公司表4.3 角色表4.4 数据字典表4.5 工程项目表4.6 使用材料表4.7 使用材料领用表4.8 整体E-R图 五、系统展示六、核心代码6.1 查询工程项目6.2 工程物资…

Affinity Designer:超越想象,打造独一无二的设计作品!mac/win版

Affinity Designer是一款功能强大的图形设计软件&#xff0c;它拥有广泛的工具和功能&#xff0c;可以满足各种设计需求。无论是平面设计师、UI/UX设计师、插画师还是摄影师&#xff0c;Affinity Designer都能为他们提供所需的工具和支持。 Affinity Designer 软件获取 Affin…

1361:产生数(Produce)

【解题思路】 1、将数字拆分保存在数组中&#xff0c;而后转换每一位。 2、将数字变化规则保存在x、y两个一维数组中&#xff0c;x[i]到y[i]是一种转换规则。 3、从n的初始值开始搜索&#xff0c;对n做数字拆分&#xff0c;将拆分后的各位数字保存在一个数组中。针对数组中的每…

数字化工厂有哪些典型应用?

随着科技的飞速发展&#xff0c;数字化工厂已经成为现代制造业的重要趋势。它将先进的数字化技术应用于制造过程&#xff0c;实现了生产流程的智能化、自动化和高效化&#xff0c;为制造业带来了革命性的变革。本文将深入探讨数字化工厂的典型应用&#xff0c;并揭示其如何推动…