B树
B树（），是一种在计算机科学自平衡的树，能够高效的存储与访问键值对数据，但要求键数据类型上存在一全序。這種資料結構能够在對數時間內完成查找數據、插入數據及刪除的操作，与此同时还可以提供对数据的有序遍历。B树，概括来说是一个一般化的二元搜尋樹，而每個節點可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。由于B树允许存在超过2个子节点，其…
标签：#B树
共 4 篇文章
红黑树
红黑树（）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为「对称二叉B树」，它现代的名字源于利奧尼達斯·J·吉巴斯和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在\text{O}(\log n)时间内完成查找、插入和删除，这里的n是树中元素的数目。 歷史 1972年，鲁道夫·拜尔發明了…
B+树
B+树（）是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。 B+树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个…
2-3-4树
2-3-4树（）在计算机科学中是阶为4的B树。 大体同B树，2-3-4树是一种自平衡数据结构，可用於實作字典。它可以在\text{O}(\log n)时间内查找、插入和删除，这里的n是树中元素的数目。 2-3-4树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。 背景 2-3-4树把数据存储在叫做元素的单独单元中。它们组合成节点，每个节点都是下列之一 2-节点，就是说，它…