《数据结构》中B-树的删除算法的实现

B-树是一种平衡的多路查找树,在文件系统中有着很好的应用。该文分析了在B-树中删除一个关键词的几种情形,给出了B-树删除算法的具体实现,有助于对《数据结构》课程中B-树操作的更好理解。     

NTFS索引目录B-树结构解析及其应用

针对一些有关NTFS文件系统的书籍和杂志中认为NTFS文件系统对索引目录的管理是采用B+树结构,通过对NTFS文件系统元文件$MFT文件夹记录的90H属性、A0H属性和B0H属性以及索引结点结构的分析,以实验的方式对索引文件进行查找、删除和插入运算来观察NTFS索引目录结构变化. 实验结果表明：NTFS文件系统对索引目录的管理是采用B-树结构,但并非是一棵标准的B-树.     

一种新的删除HB(k)树的结点的算法

Foster的删除HB(k)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除HB(k)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Foster的删除HB(k)树的结点的算法相比,新算法不涉及辅助栈的使用。设n是HB(k)树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的删除HB(k)树的结点的算法的相同。实验结果表明新算法的平均执行时间比Foster的删除HB(k)树的结点的算法短。新算法的空间复杂性是O(1),比Foster的删除HB(k)树的结点的算法低。     

一种新的删除HB(κ)树的结点的算法

Foster的删除HB(κ)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退.提出一种新的删除HB(κ)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退.举例说明新算法的执行过程.证明新算法是正确的.与Foster的删除HB(κ)树的结点的算法相比,新算法不涉及辅助栈的使用.设n是HB(κ)树的结点的个数.新算法的时间复杂性是0(log2n),与Foster的删除HB(κ)树的结点的算法的相同.实验结果表明新算法的平均执行对间比Foster的删除HB(κ)树的结点的算法短.新算法的空间复杂性是O(1),比Foster的删除HB(κ)树的结点的算法低.     

基于QCR-树的空间索引方法

QR-树处理海量空间数据时,其深度和R-树内目录矩形的重叠面积会变大,导致查询效率降低。针对该问题采用K-means算法对索引对象进行聚类分析,构造新的聚类中心使其能处理具有多种形体的索引对象,并在QR-树中引入超结点存储聚类结果。提出一种QCR-树空间索引结构来提高查询效率,给出QCR-树的插入、删除和查询算法。实验结果表明QCR-树的查询性能优于QR-树,适用于海量数据。     

一种新的删除AVL树的结点的算法

所有传统的删除AVL树的结点的算法的主要思想都是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AVL树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与目前通常采用的Foster的算法相比,新算法不涉及辅助栈的使用。设n是AVL树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的算法相同。实验结果表明新算法的平均执行时间比Foster的算法的短。新算法的空间复杂性是O(1),比Foster的算法的低。     

DNA并行计算中的B-树数据结构的设计与实现

DNA分子特性使得DNA计算具有极大的存储密度和高度的计算并行性。不管何种计算模型,DNA分子的选择和DNA编码都十分重要。提出了DNA计算中的B-树的数据结构设计方法。首先给出了B-树定义及其操作的形式化描述,接着介绍了本计算模型采用的3D结构DNA分子——k-arms分子结构,详细给出了一棵m阶B-树的构造步骤,最后实现了其查找、插入和删除等操作。提出了DNA分子计算的3D结构和分治策略,具有一定的可扩展性和并行性,对DNA计算的其他模型有参考价值。     

基于B-树的分布式群组密钥管理机制

提出把B-树引入到管理机制中,并给出了加入胁议和离开胁议的形式化描述。B-树方案在通信开销和计算方面优于二叉树方案,并且二者的差距随着B-树阶数的增大和群组成员数目的增加而明显加大。在安全性方面,B-树方案能够抵抗联合攻击。     

基于孩子兄弟树的 FAT32 文件删除恢复算法

针对由主观或客观因素造成计算机中数据丢失的情况,提出一种Windows FAT32文件系统下基于孩子兄弟树的数据删除恢复算法。 介绍FAT32文件系统和孩子兄弟树,详细阐述了如何基于孩子兄弟树重建FAT32文件系统的目录树,快速搜索到被删除文件的目录项,并通过分析文件删除前后目录项中属性值的变化来恢复被删除的文件。     

B-树和Bloom filter相结合的IPv6路由查找算法

为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和Bloom filter相结合的IPv6路由查找算法（BTBF）。BTBF分为B-树和Bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向量的映射,将下一步链接到Bloom filter,再利用Bloom filter位数组的值映射提取下一跳。实验结果表明,BTBF算法与其他树型和Bloom filter类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。     

Insertion-safeness in balanced trees

A node in a 2-3-tree or B-tree is safe (with respect to insertion) if it has less than the maximally allowable number of keys. It is a deepest safe node if it is the deepest among all safe nodes on an access path. In this paper we analyze the probabilities for a random insertion to have its deepest safe node above the leaf level and the father-of-leaves level of its access path, using the well-known average case results of Yao (1978) for random 2-3- and B-trees. The implications of these results on various solutions proposed to support concurrent operations in 2-3-trees and B-trees are also discussed.     

Persistently cached B-trees

This paper presents an approach to enhancing B-tree indexing performance by using a replication technique called persistent caching. A notable feature of the approach is its compatibility with ordinary B-trees; it exploits only the otherwise unused area of each B-tree page, and the basic behavior of B-trees need not be changed. This paper evaluates the performance of persistently cached B-trees by showing the result of mathematical analysis and of experimental investigations.     

三阶B树的构造与应用

本文给出两种构造三阶Ｂ树的算法，证明算法的时间复杂性，并给出用三阶Ｂ权实现热力公司的数据管理实例。     

Space utilization and access path length in B-trees

B-trees are useful for the maintenance of very large indexes. In this paper a deterministic model for the computation of space utilization and access path length in B-trees is presented. The considerations include a general form of B-trees that provides underflow and overflow treatment. Results for utilization and path length for some typical B-tree situations are given.     

局域世界删除演化网络模型

针对局域世界网络演化模型对于真实网络的描述过于简化的现象,提出局域世界删除演化网络模型。在网络的演化过程中既考虑了增加节点适应度对网络结构的影响,又对节点的删除和边的删除进行了探讨。研究表明增加节点的适应度可以使新节点加入时对已有网络节点的选择不只与已有网络节点的度有关;无论是删除节点还是删除边都会增加网络中度为1及度为2节点的比例,增加网络的平均路径长度,减小网络的聚类系数;随着局域世界的增大,kmax及网络的聚类系数都会增加。因此增大局域世界能够补偿删除所带来的影响。     

紧凑(a,b)树

本文提出一种新的多叉树——紧凑(a,b)树。它通过一种整编操作对树中内结点的儿子和孙子个数之间建立制约关系。在元素个数n→∞,树结点的最大儿子个数b>>4时,使树在最坏情况下的高度和空间利用率都接近最优。它的查找运算比B类树都快,它的更新运算(插入和删除)在折算意义下,即在以整个运算序列的最坏时间为代价下,与B类树的性能相同。     

Dynamic optimization of queries in pivot-based indexing

This paper evaluates the use of standard database indexes and query processing as a way to do metric indexing in the LAESA approach. By utilizing B-trees and R-trees as pivot-based indexes, we may use well-known optimization techniques from the database field within metric indexing and search. The novelty of this paper is that we use a cost-based approach to dynamically evaluate which and how many pivots to use in the evaluation of each query. By a series of measurements using our database prototype we are able to evaluate the performance of this approach. Compared to using all available pivots for filtering, the optimized approach gives half the response times for main memory data, but much more varied results for disk resident data. However, by use of the cost model we are able to dynamically determine when to bypass the indexes and simply perform a sequential scan of the base data. The conclusion of this evaluation is that it is beneficial to create many pivots, but to use only the most selective ones during evaluation of each query. R-trees give better performance than B-trees when utilizing all pivots, but when being able to dynamically select the best pivots, B-trees often provide better performance.     

A Markov chain model for dynamic binary search tree behaviour

We present a Markov chain model for the analysis of the behaviour of binary search trees (BSTs) under the dynamic conditions of insertions and deletions. The model is based on a data structure called a lineage tree, which provides a compact representation of different BST structures while still retaining enough information to model the effect of insertions and deletions and to compute average path length and tree height. Different lineages in the lineage tree correspond to states in the Markov chain. Transition probabilities are based on the number of BST structures corresponding to each lineage. The model is based on a similar lineage tree model developed for B-trees. The BST model is not intended for practical computations, but rather as a demonstration of the generalizability of the lineage tree approach for modeling data structures such as B-trees, B*-trees, B⁺-trees, BSTs, etc.     

Height-balanced multiway trees

A typical class of structures to organize ordered files is multiway trees, among which the most widely used is the perfectly balanced B-tree. In this paper we present the new family of BMT multiway trees, which are kept balanced in height, similarly to the classical binary height balanced trees used in central memory. The height of a BMT, that is the maximum search length for a key, is shown to be a logarithmic function of the number of keys in the worst case. Updating a BMT by key insertion is studied, and a technique to keep the tree balanced is presented. A comparison between the performance of BMTs and B-trees leads to the conclusion that the two structures are roughly comparable as to search length for a key, while BMTs require less memory space than B-trees for small node sizes. The real difference between BMTs and B-tree is in rebalancing operation, which requires a work proportional to the node size in the BMTs and to the tree height in the B-tree.