首页 > 其他分享 >多路查找树

多路查找树

时间:2022-09-27 11:47:12浏览次数:50  
标签:多路 多叉树 要么 tree 查找 二叉树 节点 树是

  • 二叉树存在的问题
二叉树需要加载到内存的,如果二叉树的节点少,没有什么问题,但是如果二叉树的节点很多(比如1亿)
问题1:在构建二叉树时,需要多次进行i/o操作(海量数据存在数据库或文件中),节点海量,构建二叉树时,速度有影响 
问题2:节点海量,也会造成二叉树的高度很大,会降低操作速度
  • 多叉树
在二叉树中,每个节点有数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉树(multiway tree) 
后面我们讲解的2-3树,2-3-4树就是多叉树,多叉树通过重新组织节点,减少树的高度,能对二叉树进行优化

  • B树
B树通过重新组织节点,降低树的高度,并且减少i/o读写次数来提升效率
文件系统及数据库系统的设计者利用了磁盘预读原理,将一个节点的大小设为等于一个页(页得大小通常为4k),这样每个节点只需要一次I/O就可以完全载入 
将树的度M设置为1024,在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素, B树(B+)广泛应用于文件存储系统以及数据库系统中

  • 2-3树
2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件) 
有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点.  
有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点. 
2-3树是由二节点和三节点构成的树
  • 应用实例
将数列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 构建成2-3树,并保证数据插入的大小顺序

# 插入规则
2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件) 
有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点.  
有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点 
当按照规则插入一个数到某个节点时,不能满足上面三个要求,就需要拆,先向上拆,如果上层满,则拆本层,拆后仍然需要满足上面3个条件。  
对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则

  • 2-3-4树

  • B树简介

B-tree树即B树,B即Balanced,平衡的意思。有人把B-tree翻译成B-树,容易让人产生误解。会以为B-树是一种树,而B树又是另一种树。实际上,B-tree就是指的B树

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

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

标签:多路,多叉树,要么,tree,查找,二叉树,节点,树是
From: https://www.cnblogs.com/chniny/p/16733982.html

相关文章

  • DOM添加、移除、移动、复制、创建和查找节点
    获取子节点  父节点.children  父节点.childNodes获取父节点  子节点.parentNode  子节点.offsetParent创建  document.createElement(‘标签名’)  document.......
  • 【code基础】HashMap在查找和降低时间复杂度方面的应用
    HashMap由于使用key:value形式,可以实现快速查找。通常能将时间复杂度降维//2.进阶:你可以想出一个时间复杂度小于O(n2)的算法吗?使用哈希表publicint[]two......
  • Linux常用基本命令(搜索查找类)
    搜索查找类4.1find查找文件或者目录find指令将从指定目录向下递归地遍历其各个子目录,将满足条件的文件显示在终端。1)基本语法find[搜索范围][选项]2)选项说明......
  • tomcat官网查找旧版本
    1、进入tongcat官网2、点击边栏的 3、这里有各种版本总包 4、这里有版本的细分 5、 6、找到适合自己的包 ......
  • 二叉树查找和删除指定结点
    二叉树查找指定的节点前序查找的思路1.先判断当前节点的no是否等于要查找的2.如果是相等,则返回当前节点3.如果不等,则判断当前节点的左子节点是否为空,如果不为空,则递归......
  • 斐波那契查找算法
    斐波那契也称黄金分割法,通过黄金分割点找到mid值,即mid=low+F(k-1)-1 (F代表斐波那契数列)对F(k-1)-1的理解由斐波那契数列F[k]=F[k-1]+F[k-2]的性质,可以得到 (F[k]-1......
  • 树的结点查找和删除
    二叉树查找指定的节点前序查找的思路1.先判断当前节点的no是否等于要查找的2.如果是相等,则返回当前节点3.如果不等,则判断当前节点的左子节点是否为空,如果不为空,则递归......
  • 插值查找算法
    简介插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。将折半查找中的求mid索引的公式,low表示左边索引left,high表示右边索引right. key......
  • 二分查找算法
    简介只能对有序数组进行查找代码实现publicclassBinarySearch{ publicstaticvoidmain(String[]args){ //查找单个数据 intarr[]={1,8,10,8......
  • 时间复杂度、线性查找
    排序算法时间复杂度比较稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;内排序:所有排序操作都在内存......