本文主要是介绍磁盘链式存储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+树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!