。

如果我们要操作的数据集非常大#xff0c;大到内存已经没办法处理了该怎么办呢#xff1f;

试想一下#xff0c;为了要在一个拥有几十万个文件的磁盘中查找一个文本文件#xff0c;设计的…

红黑树处理数据都是在内存中考虑的都是内存中的运算时间复杂度。

如果我们要操作的数据集非常大大到内存已经没办法处理了该怎么办呢

试想一下为了要在一个拥有几十万个文件的磁盘中查找一个文本文件设计的算法需要读取磁盘磁盘寻址上万次还是读取几十次这是有本质差异的此时为了降低对外存设备的访问次数我们就需要新的数据结构来处理这样的问题B树B树n叉树。

B树、B树的本质是通过降低树的层高减少对磁盘访问次数来提升查询速度查找复杂度logm(n/m),m是叉的数量

B树与B树区别与联系

B树所有节点即存储key也存储value内存中存不下后存磁盘名称为B-Tree并没有B-树这种叫法B树只有在叶子节点存储数据value叶子节点放在磁盘中非叶子节点用来做索引key非叶子结点在内存中相比于B树B树更适合做磁盘索引在大数据的存储和查找中使用较多比如海量图像查找引擎B树和B树的结点添加、删除、查询基本相同

m/2⌉子树即最少有⌈

m/2⌉-1个关键字。

如果根不是终端结点则根结点至少有一个关键字即至少有2棵子树。

【根的关键字取值范围是[1m-1]子树的取值范围是[2,m]】所有叶子结点都出现在同一水平没有任何信息高度一致。

如果根不是终端结点则根结点至少有一个关键字即至少有2棵子树。

【根的关键字取值范围是[1m-1]】

每个关键字对应一棵子树与B树的不同具有k个子树的非叶结点包含k

终端结点包含全部关键字及相应记录的指针叶结点中将关键字按大小顺序排序并且相邻叶结点按大小顺序相互链接起来。

所有分支结点可以视为索引的索引中金包含他的各个子节点即下一级的索引块中关键字最大值及指向其子结点的指针。

B树与B树对比

在B树中叶结点包含信息所有非叶结点仅起索引作用非叶子结点中的每个索引项只是包含了对应子树最大关键字和指向该孩子树的指针不含有该关键字对应记录的存储地址。

在B树中终端结点包含全部关键字及相应记录的指针即非终端结点出现过的关键字也会在这重复出现一次。

而B树是不重复的

我们以六叉树为例我们说的6叉树是指每个节点最多可拥有的子树个数6叉树每个节点最多可拥有6颗子树而每个节点中最多存储5个数据如下图

B树(B-树)

B树添加结点只会添加在叶子结点上重点是结点满了后会发生分裂并向父结点上位。

结点数据个数M-1结点满了的情况,发生分裂把(M-1)/2处数据放到父结点其他数据分成两个结点

添加U高度1

//在内存分配的时候一定要判断当内存不够用的时候malloc/calloc就会出错node-leaf

leaf;node-keys

*node){free(node-childrens);free(node-keys);free(node);

}/*

非根结点分裂、上位发生在B树添加元素的过程中,结点满了需要先分裂再添加

btree

B树删除结点删除叶子结点和中间结点类似重点为向父结点借位再合并操作。

删除B结点其中路径中间结点“FI”的关键字数量为(M-1)/2-1个为了避免以后出现资源不足的现象需要对FI先进行借位合并

代码如下

x-childrens[idx1];left-keys[left-num]

x-keys[idx];int

SUB_M;btree_destory_node(right);//x

key前移for(iidx1;

sizeof(KEY_VALUE));node-childrens

0;return

{assert(node);free(node-keys);//free(node-childrens);free(node);

}void

0)btree_traverse(x-childrens[i]);printf(%C

x-keys[i]);}if

btree_traverse(x-childrens[i]);

}void

node-childrens[idx];btree_node*

right

rightbtree_destroy_node(right);//node

for

left;btree_destroy_node(node);}

}void

node-childrens[idx];node-keys[idx]

left-keys[left-num

right-keys[0];btree_delete_key(T,

right,

node-keys[idx];child-childrens[child-num

right-childrens[0];child-num;node-keys[idx]

right-keys[0];for

right-childrens[right-num];right-childrens[right-num]

//borrow

child-childrens[i];}child-childrens[1]

child-childrens[0];child-childrens[0]

left-childrens[left-num];child-keys[0]

node-keys[idx

{printf(\n---------------------------------\n);btree_delete(T,

key[25

i]);//btree_traverse(T.root);btree_print(T,

T.root,