磁盘链式存储B树与B+树

2024-06-16 17:32
文章标签 存储 磁盘 链式

本文主要是介绍磁盘链式存储B树与B+树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1 介绍
    • 1.1 多叉树
    • 1.2 B树的由来
  • 2 定义与性质
  • 3 B树的应用
  • 4 B树的数据结构
  • 5 B树的常规算法
    • 5.1 创建
    • 5.2 插入
    • 5.3 删除
    • 5.4 遍历
    • 5.5 二分查找
    • 5.6 打印
  • 6 B树与B+树区别

1 介绍

1.1 多叉树

多叉树是很多种,三叉树,四叉树等等,是相对于二叉树而言的;主要用来解决二叉树的层高问题。二叉树天然的有层高的问题,需要多次遍历。

1.2 B树的由来

内存不足,就要用磁盘存储数据。对于二叉排序树或红黑树层高较高,查到一个结点就是寻址一次。层高很高,寻址就很慢,所以引入了多叉树B树。
多叉树有很多种,三叉,四叉,五叉树等;btree没有区别多少叉树,即btree就指多叉树;应用程序有更多的灵活性。

2 定义与性质

多叉树等于B树,一颗M阶B树T,满足以下条件:
1 每个结点至少拥有M颗子树
2 根结点至少有两颗子树。
3 除根结点外,其余的每个分支结点至少拥有M/2颗子树。
4 所有叶子结点都在同一层==》保证平衡树
5 有k课子树的分支结点,则存在k-1个关键字,关键字按照递增进行排序。
6 关键字数量满足 ceil(M/2) -1 <= n <= M-1
注意:实现设计时候
//度:t
//阶:2t
//结点最大元素: 2t-1

3 B树的应用

B树主要用于索引,主要是用在磁盘存储。
对于磁盘内部结构如下图:
在这里插入图片描述
可以理解为一个扇区就相当于一个结点。

4 B树的数据结构

typedef int KEY_VALUE;#define DEGREE 3typedef struct _btree_node {KEY_VALUE *keys;//结点里面有多少个树,数组struct _btree_node **childrens;//多少阶int num;//当前结点有多少结点int leaf;//是否叶子结点 yes:1 no:0
}btree_node;//b tree
typedef struct _btree{btree_node *root;int degree;
}btree;

内部函数:

//创建结点
//创建结点 degree:阶数 leaf:是否是叶子结点
btree_node *_btree_create_node(int degree, int leaf){btree_node *node = (btree_node*)calloc(1,sizeof(btree_node));if (node == NULL) {assert(0);return NULL;}//calloc = malloc +memsetnode->leaf = leaf;node->keys = (KEY_VALUE*)calloc(1, (2*degree-1)*sizeof(KEY_VALUE));if (node->keys == NULL){free(node);return NULL;}node->childrens = (btree_node**)calloc(1, (2*degree)*sizeof(btree_node));if (node->childrens == NULL){free(node->keys);free(node);return NULL;}node->num = 0;return NULL;
}//删除结点
//销毁结点
void _btree_destroy_node(btree_node *node){if (node == NULL) return;if (node->childrens) free(node->childrens);

这篇关于磁盘链式存储B树与B+树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1067089

相关文章

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL 存储引擎 MyISAM详解(最新推荐)

《MySQL存储引擎MyISAM详解(最新推荐)》使用MyISAM存储引擎的表占用空间很小,但是由于使用表级锁定,所以限制了读/写操作的性能,通常用于中小型的Web应用和数据仓库配置中的只读或主要... 目录mysql 5.5 之前默认的存储引擎️‍一、MyISAM 存储引擎的特性️‍二、MyISAM 的主

Linux lvm实例之如何创建一个专用于MySQL数据存储的LVM卷组

《Linuxlvm实例之如何创建一个专用于MySQL数据存储的LVM卷组》:本文主要介绍使用Linux创建一个专用于MySQL数据存储的LVM卷组的实例,具有很好的参考价值,希望对大家有所帮助,... 目录在Centos 7上创建卷China编程组并配置mysql数据目录1. 检查现有磁盘2. 创建物理卷3. 创

Linux给磁盘扩容(LVM方式)的方法实现

《Linux给磁盘扩容(LVM方式)的方法实现》本文主要介绍了Linux给磁盘扩容(LVM方式)的方法实现,涵盖PV/VG/LV概念及操作步骤,具有一定的参考价值,感兴趣的可以了解一下... 目录1 概念2 实战2.1 相关基础命令2.2 开始给LVM扩容2.3 总结最近测试性能,在本地打数据时,发现磁盘空

使用Python实现调用API获取图片存储到本地的方法

《使用Python实现调用API获取图片存储到本地的方法》开发一个自动化工具,用于从JSON数据源中提取图像ID,通过调用指定API获取未经压缩的原始图像文件,并确保下载结果与Postman等工具直接... 目录使用python实现调用API获取图片存储到本地1、项目概述2、核心功能3、环境准备4、代码实现

SpringBoot项目中Redis存储Session对象序列化处理

《SpringBoot项目中Redis存储Session对象序列化处理》在SpringBoot项目中使用Redis存储Session时,对象的序列化和反序列化是关键步骤,下面我们就来讲讲如何在Spri... 目录一、为什么需要序列化处理二、Spring Boot 集成 Redis 存储 Session2.1

基于MongoDB实现文件的分布式存储

《基于MongoDB实现文件的分布式存储》分布式文件存储的方案有很多,今天分享一个基于mongodb数据库来实现文件的存储,mongodb支持分布式部署,以此来实现文件的分布式存储,需要的朋友可以参考... 目录一、引言二、GridFS 原理剖析三、Spring Boot 集成 GridFS3.1 添加依赖

java变量内存中存储的使用方式

《java变量内存中存储的使用方式》:本文主要介绍java变量内存中存储的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍2、变量的定义3、 变量的类型4、 变量的作用域5、 内存中的存储方式总结1、介绍在 Java 中,变量是用于存储程序中数据

SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法

《SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法》在SQLyog中执行存储过程时出现的前置缩进问题,实际上反映了SQLyog对SQL语句解析的一个特殊行为,本文给大家介绍了详... 目录问题根源正确写法示例永久解决方案为什么命令行不受影响?最佳实践建议问题根源SQLyog的语句分

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图