B-tree(多路搜索树,并不是二叉的)是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。按照翻译,B 通常认为是Balance的简称。这个数据结构一般用于数据库的索引,综合效率较高。
另外还有一种与此类似的树结构叫B+树,像 Berkerly DB , sqlite , mysql 数据库都使用了B+树算法处理索引。
B+和B-(即B)是因为每个结点上的关键字不同。一个多一个,一个少一个。
对于B+树,其结点结构与B-tree相同,不同的是各结点的关键字和可以拥有的子结点数。如m阶B+树中,每个结点至多可以拥有m个子结点。非根结点至少有[m/2]个子结点,而关键字个数比B-tree多一个,为[m/2]~m。
这两种处理索引的数据结构的不同之处:
1。B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有可能重复出现,以维持B+树的平衡。
2。因为B树键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
3。B树的查询效率与键在树中的位置有关,最大时间复杂度与B+树相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候)。而B+树的时间复杂度对某建成的树是固定的。
分享到:
相关推荐
B-Tree的C++版本,可以实现B树的建立,插入,查找,删除,本代码中默认为3阶B-Tree,通过修改宏定义,可以修改为任意阶B-Tree
简单介绍B-tree与B+tree,帮助大家对其有个深入的理解
been so successful It discusses the major variations of the B-tree, especially the B+-tree, contrasting the relatwe merits and costs of each implementatmn. It illustrates a general purpose access ...
b-tree
谷歌 B-Tree C++ 模板库 介绍 谷歌开源团队近日发布了C++ B-Tree,这是一个C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btree_map、...
BTree,B-Tree,B+Tree,BTree都是什么.doc
B-Tree代码,包含完整工程,可执行 B-Tree代码,包含完整工程,可执行
oracle优化:B-TREE索引概念。
c 语言开发b-tree数据文件索引 .zipc 语言开发b-tree数据文件索引 .zip
在Oracle中,SYSTEM表是安装数据库时自动建立的,它包含数据库的全部数据字典,存储过程、包、函数和触发器的定义以及系统回滚段。本文只讨论Oracle中最常见的索引,即是B-tree索引。
有谁不知道啥是btree 就来看看吧 btree btree
数据结构中的B-TREE的实现
在现代处理器上,优化使用B tree数据结构; 达到优化数据库设计的目的
数据结构BTree B-Tree B+Tree B*Tree 的特征说明
本文从B树开始谈起,然后论述B+树、B*树,最后谈到R 树。其中B树、B+树及B*树部分由weedge完成,R 树部分由Frankie完成,全文最终由July统稿修订完成。
Oracle-Estimate the size of B-Tree Indexes
数据结构 B-tree和B+tree的定义、查找、插入、删除
数据结构课程设计、实验报告(原创)、开题报告、C++、B-tree
基于Qt和C++的B-Tree实现,优秀数据结构程序设计,新手必看! 基于Qt和C++的B-Tree实现,优秀数据结构程序设计,新手必看! 基于Qt和C++的B-Tree实现,优秀数据结构程序设计,新手必看! 基于Qt和C++的B-Tree实现,...