B-Tree和B+Tree

部分内容转载自互联网
https://en.wikipedia.org/wiki/B-tree
https://en.wikipedia.org/wiki/B%2B_tree

B-Tree

为了描述B-Tree,首先定义一条数据记录为一个二元组[key, data],key为记录的键值,对于不同数据记录,key是互不相同的;data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构:

.1. d为大于1的一个正整数,称为B-Tree的度。

.2. h为一个正整数,称为B-Tree的高度或深度。

.3. 每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d。

.4. 每个叶子节点最少包含一个key和两个指针,最多包含2d-1个key和2d个指针,叶节点的指针均为null(因叶子节点是最底层的节点,不需要再指向其他节点) 。

.5. 所有叶节点具有相同的深度,等于树高h。

.6. key和指针互相间隔,节点两端是指针,所以节点中指针比key多一个。

.7. 一个节点中的key从左到右非递减(即升序)排列。

.8. 所有节点组成树结构。

.9. 每个指针要么为null,要么指向另外一个节点。

.10. 如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(key1),其中v(key1)为node的第一个key的值。

.11. 如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于v(keym),其中v(keym)为node的最后一个key的值。

.12. 如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null,则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。

图2 是一个d=2的B-Tree示意图。

图2

由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:
首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。
B-Tree上查找算法的伪代码如下:

BTree_Search(node, key) {
if(node == null) return null;
foreach(node.key)
{
    if(node.key[i] == key) return node.data[i];
        if(node.key[i] > key) return BTree_Search(point[i]->node);
}
return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

关于B-Tree有一系列有趣的性质,例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N+1)/2),检索一个key,其查找节点个数的渐进复杂度为O(logdN)。
从这点可以看出,B-Tree是一个非常有效率的索引数据结构。
另外,由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。

B+Tree

B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比,B+Tree有以下不同点:

.1. 每个节点的指针上限为2d而不是2d+1。(上下矛盾?)

.2. 内节点不存储data,只存储key;叶子节点不存储指针。

图3 是一个简单的B+Tree示意。

图3

由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同。
这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间。


本质差别是B-Tree的每个NODE都记录了data,所以不是每次都要搜叶子节点才能拿到DATA。
B+Tree,只有叶子节点有DATA,因此,每次都要搜到叶子节点取DATA。
但是B+Tree在叶子节点上可以加指向下一个叶子节点的指针,所以范围扫描,B+Tree占优,比如排序。

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针(称为B* tree)。

图4

如图4 所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能,例如图4中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。

B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;
B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);
如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。

所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

PostgreSQL B-Tree 索引

也是一种增强版本,具体算法见
src/backend/access/nbtree/README
主要用了两篇论文中的算法,PostgreSQL的插入性能是非常有保障的.

Lehman and Yao's high-concurrency B-tree management algorithm
(P. Lehman and S. Yao,Efficient Locking for Concurrent Operations on B-Trees,
ACM Transactions on Database Systems, Vol 6, No. 4, December 1981, pp 650-670).     

a simplified version of the deletion logic described in Lanin and Shasha
(V. Lanin and D. Shasha, A Symmetric Concurrent B-Tree Algorithm,
Proceedings of 1986 Fall Joint Computer Conference, pp 380-389).    

Lehman & Yao Algorithm算法优化
添加了一个右指针(like B+Tree),以及一个upper bound value(解决了分裂的并发问题)。

Compared to a classic B-tree, L&Y adds a right-link pointer to each page,
to the page's right sibling.  It also adds a "high key" to each page, which
is an upper bound on the keys that are allowed on that page.  These two
additions make it possible detect a concurrent page split, which allows the
tree to be searched without holding any read locks (except to keep a single
page from being modified while reading it).

When a search follows a downlink to a child page, it compares the page's
high key with the search key.  If the search key is greater than the high
key, the page must've been split concurrently, and you must follow the
right-link to find the new page containing the key range you're looking
for.  This might need to be repeated, if the page has been split more than
once.

MySQL的请参考
http://tech.it168.com/a2011/0711/1216/000001216087_all.shtml

时间: 2024-10-23 22:22:17

B-Tree和B+Tree的相关文章

比如窗口左边是Tree,右边根据Tree的不同事件,显示不同的子窗口

问题描述 比如窗口左边是Tree,右边根据Tree的不同事件,显示不同的子窗口比如MFC写的如下:1:2: 解决方案 解决方案二:每个子节点定义好相应的NavigationUrl(记得不是很清楚),即可实现点击跳转解决方案三:publicclassForm1{SplitContainersp=newSplitContainer();TreeViewtree=newTreeView();privatevoidForm1_Load(objectsender,System.EventArgse){tr

大数据索引技术 - B+ tree vs LSM tree

MySQL索引背后的数据结构及算法原理, http://www.codinglabs.org/html/theory-of-mysql-index.html HBase Architecture, http://duanple.blog.163.com/blog/static/70971767201191661620641/ 数据库如何抵抗随机IO:问题.方法与现实, http://wangyuanzju.blog.163.com/blog/static/13029201132154010987

JSP中使用EasyUI实现异步加载tree(整合Struts 2)

首先jsp页面有一ul用于展现Tree <ul id="mytree"></ul> 加载Tree <script type="text/javascript"> $('#mytree').tree({ url:'treeLoad.action' }); </script> 配置Action <struts> <package name="tree_json" extends=&qu

C++实现树形选择排序 (tree selection sort)

算法逻辑: 根据节点的大小, 建立树, 输出树的根节点, 并把此重置为最大值, 再重构树. 因为树中保留了一些比较的逻辑, 所以减少了比较次数. 也称锦标赛排序, 时间复杂度为O(nlogn), 因为每个值(共n个)需要进行树的深度(logn)次比较. 参考<数据结构>(严蔚敏版) 第278-279页. 树形选择排序(tree selection sort)是堆排序的一个过渡, 并不是核心算法. 但是完全按照书上算法, 实现起来极其麻烦, 几乎没有任何人实现过. 需要记录建树的顺序, 在重构时

CSU 1414: Query on a Tree

预处理每个结点的子结点的个数sons , 则对x的询问可由sons[x]- sigma( sons[v] ) (v是到x距离为d的点)得到 怎么快速的找到这些v呢? 注意到距离x为d的点肯定在树的同一层.... 可以对树进行dfs时记录每个结点时间戳的同时把每一层的结点保存下来,然后对每一层维护一个前缀和 如果v是x下面子结点那么v的时间戳肯定在x的范围内,这样就可以二分確定出前缀和的范围了..... 1414: Query on a Tree Time Limit: 3 Sec  Memory

Flex tree基于数据库的数据源

最近在研究flex,关于flex tree基于数据库数据的网上的例子基本没有,大部分都是基 于xml的对xml的操作实现tree的改变,通过改变数据库数据实现tree的改变例子没有找到, 所以分享给大家一个例子: 我是用hessian实现flex端与java端通讯的 1.flex端代码 Java代码 <?xml version="1.0" encoding="utf-8"?> <mx:Application xmlns:mx="http:

UVa 10247 Complete Tree Labeling:组合数学&amp;amp;高精度

10247 - Complete Tree Labeling Time limit: 15.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1188 A complete k-ary tree is a k-ary tree in which all leaves have same d

UVa 152 Tree&#039;s a Crowd (暴力)

152 - Tree's a Crowd Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=98&page=show_problem&problem=88 Dr William Larch, noted plant psychologist and inventor of the phrase ``Think like

UVa 112 Tree Summing (scanf()去空格&amp;amp;递归&amp;amp;二叉树遍历)

112 - Tree Summing Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=48 Background LISP was one of the earliest high-level programming languages and, with FORTRAN, is one o

线段树(Segment Tree)

1.概述 线段树,也叫区间树,是一个完全二叉树,它在各个节点保存一条线段(即"子数组"),因而常用于解决数列维护问题,基本能保证每个操作的复杂度为O(lgN). 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点. 对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b].因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度. 使用线段树可以