`
dip_hu
  • 浏览: 1820 次
  • 性别: Icon_minigender_1
  • 来自: 廈門
最近访客 更多访客>>
社区版块
存档分类
最新评论

B 树、B-树、B+树、B*树

阅读更多

B

       即二叉搜索树:

       1. 所有非叶子结点至多拥有两个儿子( Left Right);

       2. 所有结点存储一个关键字;

       3. 非叶子结点的左指针指向小于其关键 字的子树,右指针指向大于其关键字的子树;

       如:

 

       B树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等, 那么就命中;

否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入

右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;

       如果 B树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么 B

的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变 B树结构

(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;

       如:

      

   但 B树在经过多次插入与删除后,有可能导致不同的结构:

   右边也是一个B树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的

树结构索引;所以,使用 B树还要考虑尽可能让 B树保持左图的结构,和避免右图的结构,也就

是所谓的“平衡”问题;       

       实际使用的 B树都是在原 B树的 基础上加上平衡算法,即“平衡二叉树”;如何保持 B

结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法 是一种在 B树中插入和删除结点的

策略;

 

 

B-

       是一种多路搜索树(并不是二叉的):

       1. 定义任意非叶子结点最多只有 M个儿子;且 M>2

       2. 根结点的儿子数为 [2, M]

       3. 除根结点以外的非叶子结点的儿子数 为 [M/2, M]

       4. 每个结点存放至少 M/2-1(取上整)和至多 M-1个关键字;(至少 2个关键字)

       5. 非叶子结点的关键字个数 =指向儿子的指针个数 -1

       6. 非叶子结点的关键字: K[1], K[2], …, K[M-1];且 K[i] < K[i+1]

       7. 非叶子结点的指针: P[1], P[2], …, P[M];其中 P[1]指向关键字小于 K[1]

子树, P[M]指向关键字大于 K[M-1]的子树,其它 P[i]指向关键字属于 (K[i-1], K[i])的子树;

       8. 所有叶子结点位于同一层;

       如:( M=3

       B-树的搜索,从根结点开 始,对结点内的关键字(有序)序列进行二分查找,如果

命中则结束,否则进入查询关键字所属范围的儿子结点; 重复,直到所对应的儿子指针为

空,或已经是叶子结点;

B-树的特性:

       1. 关键字集合分布在整颗树中;

       2. 任何一个关键字出现且只出现在一个 结点中;

       3. 搜索有可能在非叶子结点结束;

       4. 其搜索性能等价于在关键字全集内做 一次二分查找;

       5. 自动层次控制;

       由于限制了除根结点以外的非叶子结点, 至少含有 M/2个儿子,确保了结点的至少

利用率,其最底搜索性能为:

 

       其中, M为设定的非叶子结点最多子树个数, N为关键字总数;

       所以 B-树的性能总是等价于二分查找(与 M值无关),也就没有 B树 平衡的问题;

       由于 M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占

M/2的结点;删除结点时,需将两个不足 M/2的兄弟结点合并;

 

 

B+

       B+ 树是 B-树的变体,也是一种多路搜索树:

       1. 其定义基本与 B-树同,除了:

       2. 非叶子结点的子树指针与关键字个数 相同;

       3. 非叶子结点的子树指针 P[i],指向关键字值属于 [K[i], K[i+1])的子树

B-树是开区间);

       5. 为所有叶子结点增加一个链指针;

       6. 所有关键字都在叶子结点出现;

       如:( M=3

   B+的搜索与 B-树也基本相同,区别是 B+树只有达到叶子结点才命中( B-树可以在

非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

       B+ 的特性:

       1. 所有关键字都出现在叶子结点的链表 中(稠密索引),且链表中的关键字恰好

是有序的;

       2. 不可能在非叶子结点命中;

       3. 非叶子结点相当于是叶子结点的索引 (稀疏索引),叶子结点相当于是存储

(关键字)数据的数据层;

       4. 更适合文件索引系统;

 

B*

       B+树的变体,在 B+树 的非根和非叶子结点再增加指向兄弟的指针;

   B*树定义了非叶子结点关键字个数至少为 (2/3)*M,即块的最 低使用率为 2/3

(代替 B+树的 1/2);

       B+ 树的分裂:当一个结点满时,分配一 个新的结点,并将原结点中 1/2的数据

复制到新结点,最后在父结点中增加新结点的指针; B+树的分裂只影响原结点和父

结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

       B* 树的分裂:当一个结点满时,如果它 的下一个兄弟结点未满,那么将一部分

数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字

(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之

间增加新结点,并各复制 1/3的数据到新结点,最后在父结点增加新结点的指针;

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

 

小结

       B 树:二叉树,每个结点只存储一个关键 字,等于则命中,小于走左结点,大于

走右结点;

       B- 树:多路搜索树,每个结点存储 M/2 M个关键字,非 叶子结点存储指向关键

字范围的子结点;

       所有关键字在整颗树中出现,且只出现一 次,非叶子结点可以命中;

       B+ 树:在 B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点

中出现,非叶子结点作为叶子结点的索引; B+树总是到叶子结点才命中;

       B* 树:在 B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率

1/2提高到 2/3

 原文地址 http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx

分享到:
评论

相关推荐

    B树-B+树-B*树谈到R树

    ### B树-B+树-B*树谈到R树 #### 一、引言 在计算机科学领域,树形数据结构作为一种高效的数据组织方式被广泛应用。在众多树形结构中,B树、B+树、B*树和R树因其在处理大规模数据集时表现出的优秀性能而备受关注。...

    B-树、B+树、B树详解

    B树、B-树、B+树以及B*树都是基于树形结构的自平衡数据结构,它们各有侧重,适用于不同的应用场景: - **B树** 更适合需要频繁插入和删除操作的场景。 - **B-树** 保证了较高的查找效率,适用于对查找速度要求较高的...

    B树、B-树、B+树、B树

    ### B树、B-树、B+树、B树算法实现及原理 #### B树(Balanced Tree) **定义:** B树是一种自平衡的树数据结构,它能够保持数据排序,且查找、插入和删除操作的时间复杂度均为O(log n)。B树非常适合用于实现虚拟...

    B树、B-树、B+树、B树++、R-tree总结

    B树++(B*树)是对B+树的进一步优化,增加了节点的扇出率,减少了节点分裂和合并的频率,提高了空间利用率。 R树(R-tree)是一种多维空间索引结构,用于处理高维数据,如地理信息系统中的坐标数据。R树允许节点...

    工程实践2--B+树.rar

    在IT领域,B+树(B Plus Tree)是一种重要的数据结构,广泛应用于数据库管理系统和文件系统中,以高效地处理大量的数据。B+树的主要特点是平衡性和数据存储的有序性,使得查找、插入和删除操作的性能保持在一个相对...

    b+b-树c语言版

    本压缩包“b+b-树c语言版”提供了C语言实现的B+树相关功能,包括创建、删除、查询和插入操作。以下是关于B+树及其C语言实现的详细知识。 **B+树简介** B+树(B Plus Tree)是一种自平衡的树,它的设计目的是为了...

    B+树讲义(英文)

    根据给定文件的信息,我们可以深入探讨B+树这一数据结构的关键知识点,以及它在数据库系统中的应用和特性。 ### B+树概述 B+树是一种自平衡的树数据结构,常用于实现虚拟内存、文件系统和数据库索引。它是由Rudolf...

    从B树、B+树、Bx树谈到R树

    ### 从B树、B+树、B*树到R树:深入了解数据结构的应用 #### 一、前言 在大规模数据存储与检索领域,树形数据结构扮演着至关重要的角色。传统二叉查找树虽然提供了较为高效的查找性能,但由于其高度与数据量成正比...

    B-树与B+树(重要)1

    B-树和B+树是两种重要的数据结构,主要用于数据库和文件系统的索引,它们能够高效地处理大量的数据,尤其适合磁盘等慢速存储介质。这两种数据结构都是多路平衡查找树,能够保持数据的有序性,同时通过减少磁盘I/O...

    B.rar_B+树_B+树 C++实现_B树_visual c

    **B+树详解** B+树(B Plus Tree)是一种自平衡的树数据结构,广泛应用于数据库和文件系统中,因为它能保持数据有序并提供高效的数据检索。B+树的主要特性在于其节点可以包含多个键,并且每个节点的子节点数量与键...

    b+/-树的实现源代码

    **B+树与B-树概述** B+树和B-树是计算机科学中用于数据库和文件系统等数据存储的重要数据结构,它们主要用于高效地管理大量数据,特别是当数据需要在磁盘等慢速存储介质上进行操作时。这两种树都是自平衡的,能保持...

    B+树的c语言代码实现

    ### B+树C语言代码实现解析 #### 一、引言 本文将深入解析一份C语言实现的B+树代码,这份代码不仅演示了如何在操作系统文件系统之上构建B+树,而且还展示了如何通过文件操作来模拟B+树的建立过程。通过分析这段代码...

    B-树和B+树_C语言实现B+树_算法_B+B-B_数据结构_B+树_

    B-树和B+树的C语言实现(数据结构)。

    B-树和B+树的源代码

    B-树(Balanced Tree)和B+树是两种常见的自平衡的多路搜索树,广泛应用于数据库和文件系统中,以优化大容量数据的访问效率。这两种数据结构都是为了在磁盘等慢速存储设备上实现高效的查找、插入和删除操作。 B-树...

    从B树、B+树、B*树谈到R树

    标题中的“从B树、B+树、B*树谈到R树”涵盖了数据库索引结构中的几种重要数据结构。这些数据结构在存储和检索大量数据时起着关键作用,尤其在数据库管理系统、文件系统和地理信息系统等领域。让我们逐一探讨这些数据...

    B 树、 B- 树、 B+ 树、 B 树都是什么 .doc

    B树、B-树、B+树和B*树都是数据库和文件系统中常用的高效数据结构,它们主要用于解决大数据量的存储和检索问题。这些数据结构都是多路搜索树,与二叉搜索树不同的是,它们的每个节点可以有多个子节点,从而允许更...

    从B_树、B+_树、B_树谈到R_树.doc

    【B树、B+树和B*树:数据结构中的高效索引技术】 在计算机科学中,数据结构的选择对算法的效率至关重要。特别是在处理大规模数据时,如何有效地存储和检索信息是一个关键问题。B树(B-tree)、B+树(B+tree)和B*树...

    二叉树、B树、B+树、红黑树

    ### 二叉树、B树、B+树、红黑树 #### 一、二叉树 二叉树是一种常见的树形数据结构,在计算机科学中应用广泛。它具有以下特点: - **节点最多有两个子节点**:即每个节点最多有一个左子节点和一个右子节点。 - **...

    Introduction to Algorithms, 3rd edtion

    - **B**:集合等 - **C**:计数与概率 - **D**:矩阵 #### 六、总结 《算法导论》是一部全面深入介绍算法设计与分析的经典著作,覆盖了从基础知识到高级主题的广泛内容。该书不仅提供了丰富的算法实例,还详细介绍...

    B树和B+树的插入、删除图文详解 - nullzx - 博客园1

    在探讨数据库和文件系统中数据结构的高效管理时,B树和B+树的讨论是无法绕开的话题。这两种多路平衡查找树不仅在理论上具有深厚的基础,而且在实际应用中也显示出了极高的效率和可靠性。本文将详细解析B树和B+树在...

Global site tag (gtag.js) - Google Analytics