论文标题
b-tree结构的合掩例表示
Cache-Oblivious Representation of B-Tree Structures
论文作者
论文摘要
我们提出了一个通用数据结构CorOBTS，用于以合并的方式将van emde boas内存布局与包装的内存数组组合在一起，以合并的方式存储B-Tree样搜索树。 到目前为止，在使用VEB布局的使用中，主要考虑了搜索复杂性。我们展示了对子树和连续内存区域的深度优先搜索的复杂性，并可以更好地了解树在树和内存中的顶点位置之间的关系。如果我们可以模拟其深度优点搜索，我们将描述如何在VEB布局中构建任意树。同样，我们检查了包装的内存数组的批处理更新。 在Corobts中，存储的搜索树必须满足所有叶子的深度，并且顶点在所选常数$ a $ a $ a $ a和$ b $之间。数据结构允许使用最佳I/O复杂性$ \ MATHCAL {O}（\ log_b {n}）$搜索，并存储在线性空间中。它提供了插入和删除子树的操作； both have an amortized I/O complexity $\mathcal{O}(S\cdot(\log^2 N)/B + \log_B N\cdot\log\log S + 1)$ and amortized time complexity $\mathcal{O}(S\cdot\log^2 N)$, where $S$ is the size of the subtree and $N$ the size of the whole stored tree.如果没有更改单个树级别上的顶点数量，则重建现有子树在两个复杂性中保存乘法$ \ Mathcal {o}（\ log^2 n）$。否则，它仅用于插入/删除的顶点。 Davoodi等人提出的一定持久阵列修改合并缓存的阵列。 [ESA，第296-308页。 Springer，2014年]要使用corobts，将其空间复杂性从$ \ Mathcal {o}（u^{\ log_2 3} + v \ log u）$ to $ \ mathcal {o}（u + v \ log u）$，在$ u $的地方，$ u $是阵列和$ v $的最大大小。当前和持续读取的数据局部性以及I/O的复杂性保持不变； i/o写入的复杂性通过一个多组分因子恶化。
We propose a general data structure CORoBTS for storing B-tree-like search trees dynamically in a cache-oblivious way combining the van Emde Boas memory layout with packed memory array. In the use of the vEB layout mostly search complexity was considered, so far. We show the complexity of depth-first search of a subtree and contiguous memory area and provide better insight into the relationship between positions of vertices in tree and in memory. We describe how to build an arbitrary tree in vEB layout if we can simulate its depth-first search. Similarly, we examine batch updates of packed memory array. In CORoBTS, the stored search tree has to satisfy that all leaves are at the same depth and vertices have arity between the chosen constants $a$ and $b$. The data structure allows searching with an optimal I/O complexity $\mathcal{O}(\log_B{N})$ and is stored in linear space. It provides operations for inserting and removing a subtree; both have an amortized I/O complexity $\mathcal{O}(S\cdot(\log^2 N)/B + \log_B N\cdot\log\log S + 1)$ and amortized time complexity $\mathcal{O}(S\cdot\log^2 N)$, where $S$ is the size of the subtree and $N$ the size of the whole stored tree. Rebuilding an existing subtree saves the multiplicative $\mathcal{O}(\log^2 N)$ in both complexities if the number of vertices on individual tree levels is not changed; it is paid only for the inserted/removed vertices otherwise. Modifying cache-oblivious partially persistent array proposed by Davoodi et al. [ESA, pages 296-308. Springer, 2014] to use CORoBTS improves its space complexity from $\mathcal{O}(U^{\log_2 3} + V \log U)$ to $\mathcal{O}(U + V \log U)$, where $U$ is the maximal size of the array and $V$ is the number of versions; the data locality and I/O complexity of both present and persistent reads are kept unchanged; I/O complexity of writes is worsened by a polylogarithmic factor.
