Maintaining Dictionaries: Space-Saving Modifications of B-Trees
Maintaining Dictionaries: Space-Saving Modifications of B-Trees
复制标题
维护字典：B 树的节省空间的修改
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
K. Shvachko
中科院分区：
文献类型：
--
作者：
A. 0. Pinchuk;K. Shvachko
众所周知，当键的长度彼此差异很大时，B树的数据结构会导致内存的极大浪费。这种影响可以通过对数据结构进行适当修改来解决。我们引入了一种B树的变体，称为键长不固定的B树，并将它与T.H.马丁引入的另一种B树变体（我们称之为键长有界的B树）进行比较。在最坏情况下评估了这两种变体的空间效率。然而，更符合实际的平均情况下的效率仍然未知。我们认为，在许多应用中，键长不固定的B树更高效。
It is known that the data structure of B-trees leads to an exhaustive waste of memory, when lengths of keys differ very much from each other. This effect may be fixed with appropriate modifications of (he data structure. We introduce a variant of B-trees, called B-trees with unfixed key length, and compare it to another variant of B-trees, introduced by T.H. Martin, which we call B-trees with bounded key length. Space efficiency of those two variants is evaluated for the worst case. However, the efficiency for the more realistic average case remains unknown. We believe that in many applications B-trees with unfixed key length are more efficient.