Cross-Referenced Dictionaries and the Limits of Write Optimization
Cross-Referenced Dictionaries and the Limits of Write Optimization
复制标题
DOI：
10.1137/1.9781611974782.99
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
P. Afshani;M. A. Bender;Martín Farach-Colton;Jeremy T. Fineman;Mayank Goswami;M. Tsai
中科院分区：
文献类型：
--
作者：
P. Afshani;M. A. Bender;Martín Farach-Colton;Jeremy T. Fineman;Mayank Goswami;M. Tsai
字典仍然是数据结构中研究最为深入的一类。字典支持插入、删除、成员资格查询，通常还支持后继、前驱以及提取最小值操作。在随机存取存储器（RAM）中，对于N个元素，所有这些操作都需要O(log N)时间。字典经常如下交叉引用。考虑一组元组{〈ai, bi, ci...〉}。一个数据库可能在此类集合上包含不止一个字典，例如，一个以a为索引，另一个以b为索引，以此类推。再次说明，在随机存取存储器中，向一组L个交叉引用的字典中插入元素需要O(L log N)时间，删除操作也是如此。在外部存储器中的情况则更有趣。在磁盘访问机（DAM）上，B树在单个字典上进行插入和删除操作时实现O(logB N)次I/O操作，K个元素的范围查询实现最优的O(logB N + K/B)次I/O操作。这些界限对于交叉引用字典上的B树也是可实现的，只是在插入和删除操作上会有L倍的减速。近年来，外部存储器字典的理论和实践都因写优化技术而发生了变革。如果一个字典在查询时间上接近B树，同时在插入操作上优于B树，那么它就是写优化的。最好的（也是最优的）字典在单个字典上实现了显著改进的插入和删除成本为[公式]，0 ≤ e ≤ 1，平摊I/O操作，同时保持最优的O(log1+Be N + K/B) - I/O范围查询。尽管写优化对于交叉引用字典的插入操作仍然有帮助，但其对于删除操作的价值似乎大大降低了。对交叉引用字典的一次删除操作只指定一个键a。似乎有必要查找相关的值b、c...以便从其他字典中删除它们。这需要Ω(logB N)次I/O操作，远高于每个字典的写优化预算[公式]次I/O操作。所以总的删除成本是[公式]次I/O操作。简而言之，对于删除操作，写优化相对于B树的优势在于L乘以一个低阶项，但当L = 2时，写优化相对于B树似乎没有渐近优势。也就是说，对于成对的交叉引用字典，没有已知的查询最优解决方案在删除操作上似乎优于B树。在本文中，我们给出了一个下界，证明了一对对于范围查询是最优且支持删除操作的交叉引用字典无法匹配仅用于插入操作的字典所能达到的写优化界限。这个结果因此确定了许多新数据库和文件系统所基于的写优化技术的适用性限制。
Dictionaries remain the most well studied class of data structures. A dictionary supports insertions, deletions, membership queries, and usually successor, predecessor, and extract-min. In a RAM, all such operations take O(log N) time on N elements. Dictionaries are often cross-referenced as follows. Consider a set of tuples {〈 ai, bi, ci ...〉 }. A database might include more than one dictionary on such a set, for example, one indexed on the a's, another on the b's, and so on. Once again, in a RAM, inserting into a set of L cross-referenced dictionaries takes O(L log N) time, as does deleting. The situation is more interesting in external memory. On a Disk Access Machine (DAM), B-trees achieve O(logB N) I/Os for insertions and deletions on a single dictionary and K-element range queries take optimal O(logB N + K/B) I/Os. These bounds are also achievable by a B-tree on cross-referenced dictionaries, with a slowdown of an L factor on insertion and deletions. In recent years, both the theory and practice of external memory dictionaries has been revolutionized by write optimization techniques. A dictionary is write optimized if it is close to a B-tree for query time while beating B-trees on insertions. The best (and optimal) dictionaries achieve a substantially improved insertion and deletion cost of [EQUATION], 0 ≤ e ≤ 1, amortized I/Os on a single dictionary while maintaining optimal O(log1+Be N + K/B)- I/O range queries. Although write optimization still helps for insertions into cross-referenced dictionaries, its value for deletions would seem to be greatly reduced. A deletion into a cross referenced dictionary only specifies a key a. It seems to be necessary to look up the associated values b, c... in order to delete them from the other dictionaries. This takes Ω(logB N) I/Os, well above the per-dictionary write optimization budget of [EQUATION] I/Os. So the total deletion cost is [EQUATION] I/Os. In short, for deletions, write optimization offers an advantage over B-trees in that L multiplies a lower order term, but when L = 2, write optimization seems to offer no asymptotic advantage over B-trees. That is, no known query-optimal solution for pairs of cross-referenced dictionaries seem to beat B-trees for deletions. In this paper, we show a lower bound establishing that a pair of cross-referenced dictionaries that are optimal for range queries and that supports deletions cannot match the write optimization bound available to insert-only dictionaries. This result thus establishes a limit to the applicability of write-optimization techniques on which many new databases and file systems are based.