A comparison of adaptive radix trees and hash tables
A comparison of adaptive radix trees and hash tables
复制标题
自适应基数树和哈希表的比较
DOI：
10.1109/icde.2015.7113370
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Dittrich
中科院分区：
文献类型：
--
作者：
V. Álvarez;Stefan Richter;Xiao Chen;J. Dittrich
随着主存储器价格的不断下降，人们现在更感兴趣的是在主存储器中执行计算，并将传统基于磁盘的系统的高I/O成本排除在外。然而，这种范式的变化对数据在主存中的存储和索引方式提出了新的挑战，以便有效地处理数据。传统的数据结构，如古老的B树，是为在基于磁盘的系统上工作而设计的，但它们不再是主存系统的主流，至少不是它们原来的形式，因为它们所运行的系统的缓存利用率很低。正因为如此，特别是在过去的十年里，有相当多的关于主存系统索引数据结构的研究。在最近和最有趣的数据结构的主存系统中，有最近提出的自适应基数树ARTful（简称ART）。ART的作者提出的实验表明，ART显然是比其他最近的基于树的数据结构（如FAST和B+树）更好的选择。然而，ART并不是第一个自适应基数树。据我们所知，第一个是朱迪阵列（简称朱迪），ART和朱迪之间的比较没有显示。此外，同一组实验表明，只有哈希表才能与ART竞争。ART的作者在他们的研究中使用的哈希表是链式哈希表，但这种哈希表在空间和性能方面可能是次优的，因为它们潜在地大量使用指针。在本文中，我们提出了一个彻底的实验比较ART，朱迪，通过二次探测散列的两个变种，和布谷鸟散列的三个变种。这些散列方案被认为是非常有效的。在我们的研究中，我们考虑数据结构是用作非覆盖索引（依赖于额外的存储），还是用作覆盖索引（覆盖键值对）。我们同时考虑OLAP和OLTP场景。我们的实验强烈表明，ART和Judy在性能方面都不能与上述哈希方案竞争，在ART的情况下，有时甚至在空间方面也不能。
With prices of main memory constantly decreasing, people nowadays are more interested in performing their computations in main memory, and leave high I/O costs of traditional disk-based systems out of the equation. This change of paradigm, however, represents new challenges to the way data should be stored and indexed in main memory in order to be processed efficiently. Traditional data structures, like the venerable B-tree, were designed to work on disk-based systems, but they are no longer the way to go in main-memory systems, at least not in their original form, due to the poor cache utilization of the systems they run on. Because of this, in particular, during the last decade there has been a considerable amount of research on index data structures for main-memory systems. Among the most recent and most interesting data structures for main-memory systems there is the recently-proposed adaptive radix tree ARTful (ART for short). The authors of ART presented experiments that indicate that ART was clearly a better choice over other recent tree-based data structures like FAST and B+-trees. However, ART was not the first adaptive radix tree. To the best of our knowledge, the first was the Judy Array (Judy for short), and a comparison between ART and Judy was not shown. Moreover, the same set of experiments indicated that only a hash table was competitive to ART. The hash table used by the authors of ART in their study was a chained hash table, but this kind of hash tables can be suboptimal in terms of space and performance due to their potentially high use of pointers. In this paper we present a thorough experimental comparison between ART, Judy, two variants of hashing via quadratic probing, and three variants of Cuckoo hashing. These hashing schemes are known to be very efficient. For our study we consider whether the data structures are to be used as a non-covering index (relying on an additional store), or as a covering index (covering key-value pairs). We consider both OLAP and OLTP scenarios. Our experiments strongly indicate that neither ART nor Judy are competitive to the aforementioned hashing schemes in terms of performance, and, in the case of ART, sometimes not even in terms of space.
关于使用带有简单通用哈希类的布谷鸟哈希的风险
DOI：
10.1137/1.9781611973068.87
发表时间：
2009
期刊：
影响因子：
--
作者：
Martin Dietzfelbinger;Ulf Schellbach
通讯作者：
Ulf Schellbach