B-TREE(B-树)

这篇具有很好参考价值的文章主要介绍了B-TREE(B-树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

B-TREE

B-tree 又叫平衡多路查找树。一棵 m 阶的 B-tree (m 叉树)的特性如下(其中 ceil(x)是一个取上限的函数):

  1. 树中每个结点至多有 m 个孩子;

  2. 除根结点和叶子结点外,其它每个结点至少有有 ceil(m / 2)个孩子;

  3. 若根结点不是叶子结点,则至少有 2 个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);

  4. 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点,实际上这些结点不存在,指向这些结点的指针都为 null);

  5. 每个非终端结点中包含有 n 个关键字信息: (n,P0,K1,P1,K2,P2,…,Kn,Pn)。其中:

a) Ki (i=1…n)为关键字,且关键字按顺序排序 K(i-1)< Ki。

b) Pi 为指向子树根的接点,且指针 P(i-1)指向子树种所有结点的关键字均小于 Ki,但都大于 K(i-1)。

c) 关键字的个数 n 必须满足: ceil(m / 2)-1 <= n <= m-1

B-TREE(B-树),高手面试,b树,数据结构

一棵 m 阶的 B+tree 和 m 阶的 B-tree 的差异在于:

1.有 n 棵子树的结点中含有 n 个关键字; (B-tree 是 n 棵子树有 n-1 个关键字)

2.所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (B-tree 的叶子节点并没有包括全部需要查找的信息)

3.所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。

(B-tree 的非终节点也包含需要查找的有效信息)

B-TREE(B-树),高手面试,b树,数据结构文章来源地址https://www.toymoban.com/news/detail-793476.html

到了这里,关于B-TREE(B-树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 022:vue中tree结构数据变成扁平化table结构数据的示例

    第022个 查看专栏目录: VUE ------ element UI 在vue和element UI联合技术栈的操控下,本专栏提供行之有效的源代码示例和信息点介绍,做到灵活运用。 (1)提供vue2的一些基本操作:安装、引用,模板使用,computed,watch,生命周期(beforeCreate,created,beforeMount,mounted, beforeUpdate,upda

    2024年02月12日
    浏览(44)
  • 数据结构与算法 | 二叉树(Binary Tree)

    二叉树(Binary Tree)是一种树形数据结构,由节点构成,每个节点最多有两个子节点:一个左子节点和一个右子节点。 \\\"二叉树\\\"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树

    2024年02月08日
    浏览(41)
  • 【数据结构基础】树 - 前缀树(Trie Tree)

    Trie,又称字典树、单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的

    2024年02月07日
    浏览(45)
  • 红黑树下岗,内核新数据结构上场:maple tree!

      在外界看来,Linux 内核的内部似乎变化很少,尤其是像内存管理子系统(memory-management subsystem)这样的子系统。然而,开发人员时常需要更换内部接口来解决某些长期存在的问题。比如,其中一个问题就是用来保护内存管理里的重要结构的锁的竞争问题,这些重要结构是指

    2024年02月04日
    浏览(49)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(45)
  • B-TREE(B-树)

    B-TREE B-tree 又叫平衡多路查找树。一棵 m 阶的 B-tree (m 叉树)的特性如下(其中 ceil(x)是一个取上限的函数): 树中每个结点至多有 m 个孩子; 除根结点和叶子结点外,其它每个结点至少有有 ceil(m / 2)个孩子; 若根结点不是叶子结点,则至少有 2 个孩子(特殊情况:没有孩子的

    2024年01月16日
    浏览(40)
  • Element-UI控件Tree实现数据树形结构

            在前端开发中,有时会遇到所有菜单数据在同一级的情况,后端未对数据进行分级处理;但前端渲染需要是树状结构的数据,如何实现数据的树状化?将数组中通过父节点的ID与子节点的parentId关联,通过递归函数来实现。         前端框架这里使用element-ui的tree控件

    2024年02月05日
    浏览(119)
  • 区块链的数据结构(二)——默克尔树(Merkle Tree)

            区块链中的另外一个数据结构是Merkle tree,在比特币中使用的就是这种结构:         可能没有听说过Merkle tree,但一定听说过binary tree(二叉树)。         Merkle tree和binary tree的区别:Merkle tree用哈希指针代替了普通的指针         每个框内的两个哈希值

    2024年02月21日
    浏览(44)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • 浙大数据结构第四周之04-树6 Complete Binary Search Tree

    A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node\\\'s key. The right subtree of a node contains only nodes with keys greater than or equal to the node\\\'s key. Both the left and right subtrees must also be binary search trees. A Comple

    2024年02月16日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包