`
darrenzhu
  • 浏览: 802582 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

B-树,B+树与B*树的优缺点比较

阅读更多

首先注意:B树就是B-树,"-"是个连字符号,不是减号。
B-树是一种平衡的多路查找(又称排序)树,在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance)

B+树有一个最大的好处,方便扫库,B树必须用中序遍历的方法按序扫库,而B+树直接从叶子结点挨个扫一遍就完了。

B+树支持range-query(区间查询)非常方便,而B树不支持。这是数据库选用B+树的最主要原因。

比如要查 5-10之间的,B+树一把到5这个标记,再一把到10,然后串起来就行了,B树就非常麻烦。B树的好处,就是成功查询特别有利,因为树的高度总体要比B+树矮。不成功的情况下,B树也比B+树稍稍占一点点便宜。

B树的优势是当你要查找的值处在非叶子节点时,当到该非叶节点时查找就成功并结束了,而B+树由于非叶节点只是索引部分,这些节点中只含有其子树中的最大(或最小)关键字,当非终端节点上的关键字等于给点值时,查找并不终止,而是继续向下直到叶子节点。因此在B+树中,无论查找成功与否,都是走了一条从跟到叶子节点的路径。

有很多基于频率的搜索是选用B树,越频繁query的结点越往根上走,前提是需要对query做统计,而且要对key做一些变化。
另外B树也好B+树也好,根或者上面几层因为被反复query,所以这几块基本都在内存中,不会出现读磁盘IO,一般已启动的时候,就会主动换入内存。
”mysql底层存储是用B+树实现的,因为内存中B+树是没有优势的,但是一到磁盘,B+树的威力就出来了。


B*树
是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);
B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;
所以,B*树分配新结点的概率比B+树要低,空间使用率更高;
分享到:
评论

相关推荐

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

    #### 三、B+树 (B+-Tree) **定义**: - B+树是在B-树的基础上发展起来的一种多路搜索树。 - 除了保留B-树的特点外,B+树为所有叶子节点添加了链指针,使得所有关键字仅存在于叶子节点中。 - 非叶子节点用作叶子节点...

    100期--数据结构板书+代码.zip

    7. **树**:树结构包括二叉树、平衡树(如AVL树、红黑树)、B树、B+树等,广泛应用于文件系统、数据库索引等领域。 8. **图**:图由顶点和边构成,用于表示实体之间的关系,可以用来解决最短路径、网络流等问题。 ...

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

    - **B树与B+树的区别**:B树中关键字集合分布在整棵树中,而B+树中关键字只存在于叶子节点中;B+树中的关键字在非叶节点中也会出现,以帮助快速定位。 #### 四、红黑树 红黑树是一种自平衡的二叉查找树,它通过...

    索引基础——B-Tree、B+Tree、红黑树、BTree数据结构1

    搜索时,根据关键字与目标关键字的比较来决定向左还是向右的子树搜索,直到找到目标或者搜索到空指针。这种结构使得B-Tree在插入、删除和查找操作上都有良好的性能,而且通常只需要常数级别的额外空间。 B+Tree是B-...

    The Ubiquitous B-Tree

    通过对比B树的不同变体,我们可以更好地理解它们各自的优缺点,并根据具体的应用需求选择最适合的实现方案。无论是传统的文件系统还是现代的大型数据库系统,B树及其变体都是确保数据高效访问不可或缺的技术基础。

    java外观模式.pdf

    **缺点**: - 如果子系统的接口频繁变动,那么外观类可能需要频繁修改。 - 若过度使用,可能会增加系统的抽象层次,使得系统更难理解。 ### 7. 结论 在实际开发中,外观模式是一种常用的设计模式,它简化了客户端与...

    谷歌B-Tree的C++模板库

    C ++ B-树的容器,更好地利用高速缓存的搜索树的每个节点执行多个键比较。虽然B-树算法更复杂,红 - 黑树算法相比,提高缓存的行为可以解释在访问大型容器的显着加速。 C ++ B-树的容器也不是没有缺点,但是。与...

    Modern B-Tree Techniques

    文章还对比了B-树与哈希索引的优缺点,总结了基础部分的内容。 在数据结构和算法部分,文章深入讨论了如变长记录、内插搜索、前缀B-树以及CPU缓存优化等技术。此外,还涉及了重复键值的处理、位图索引和数据压缩,...

    2008康柏世朝田液压综合样本.pdf

    - 不同类型的阀门在具体应用场景中的优缺点分析; - 在控制系统中如何正确选择和安装控制元件; - 在设计方向控制阀时需要考虑的关键因素; - 对于流量控制和压力控制的需求,如何选择合适的元件; - 过滤器的选择与...

    【转】深入研究B树索引

    ### 四、B树与B+树 B+树是B树的一个变体,它增强了B树的一些特性,更适合于数据库索引。B+树的所有数据都存储在叶子节点,且叶子节点之间通过指针连接成链表,便于全序遍历。此外,B+树的非叶子节点仅作为查找的...

    Java程序架构[归类].pdf

    Java程序架构设计是软件开发中的...不同的架构模式各有优缺点,适合不同的项目场景,选择正确的架构是确保项目成功的关键步骤。在实践中,开发人员应根据实际情况灵活应用,不断优化,以实现高效、可维护的软件系统。

    Mysql中explain作用详解

    +----+-------------+-------+--------+---------------+---------+---------+---------------------------+------+-------+ 在这个查询中,首先全表扫描了tb_order表,然后以tb_product表的主键列进行等值连接。...

    算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS

    深度优先搜索(Depth-First Search, DFS)与广度优先搜索(Breadth-First Search, BFS)是图论和算法领域中两种重要的遍历策略,常用于解决各种问题,如搜索路径、判断连通性、拓扑排序等。在面试中,熟练掌握这两种...

    数据结构与算法分析C语言描述第二版英文版

    - **B树与B+树**:讲解B树和B+树的特点及应用场景。 **第五章:哈希表** - **散列函数**:讨论设计高效散列函数的原则。 - **碰撞解决策略**:比较不同碰撞解决方法的优缺点。 **第六章:优先级队列(堆)** - *...

    二叉树数据结构扩展.pptx

    - **缺点**:当树的大小发生变化时,可能需要重新平衡。 #### 三、平衡二叉树:自平衡机制与实现 **平衡二叉树简介:** 平衡二叉树是一种特殊类型的二叉搜索树,其目的是通过维持树的高度尽可能小来提高树的操作...

    10种AD采样的软件滤波方法的优缺点

    - **缺点**:无法消除周期性干扰,且平滑度较差。 - **实现示例**: ```c void limitFilter(int newValue, int *lastValue, int A) { if (abs(newValue - *lastValue) ) { *lastValue = newValue; } } ``` #...

    南邮数据结构2001-2006

    - **缺点**:空间开销大。 **4. 二叉树的遍历与表示** - **带右链的先序遍历** - 存储结构包含节点值和指向下一个节点的指针。 - 根据给定的序列构建二叉树。 **5. AOE 网络** - **活动的最早开始时间和最晚...

Global site tag (gtag.js) - Google Analytics