1、应用背景 二叉查找树、AVL树、红黑树等都属于二叉树的范围,查找的时间复杂度是O(log 2N),与树的深度相关,那么降低树的深度自然会提高查找效率。 但是我们面对这样一个实际问题:大规模数据存储中,树节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。 因此,为了减少磁盘I/O的次数,必须降低树的深度,将“瘦高”的树变得“矮胖”。一个基本的想法就是: 每个节点存储多个元素 摒弃二叉树结…

2021年5月3日 0条评论 3点热度 阅读全文

B树、B+树、红黑树、AVL树 B树B树红黑树AVL树 定义及概念 B树 B树 红黑树 AVL树 B树和B树的区别 红黑树的应用及和B树区别 AVL树和红黑树 B树M阶的插入和删除 插入 删除 定义及概念 B树 二叉树的深度较大,在查找时会造成I/O读写频繁,查询效率低下,所以引入了多叉树的结构,也就是B树。关于B树的由来,这里阐述了B-tree名字来源以及相关的开源地址。 阶为M的B树具有以下性质: 1、根节点在不为叶子节点的情况下儿子数为 2 ~ M 2、除根结点以外的非叶子结点的儿子数为 M/2(向上取整) …

2016年9月15日 0条评论 2点热度 阅读全文