database - 自适应基数树

Question

自 1 周以来，我发现了一个有趣的话题: 自适应基数树， 我发现它是一种非常有用的技术，专门用于现代硬件架构中的内存索引。

其实我在第4页有一点没看懂，叫做Node48。

我附上了我的意思的图片。 http://s30.postimg.org/nff1am2r5/xadaptive_radix.png

这也是文章的主页:http://www-db.in.tum.de/~leis/papers/ART.pdf

所以谁能比我更聪明的人为我解释一下，我会很高兴。 谢谢。

Answer 1

我相信您了解 NODE_4 和 NODE_16 的工作原理。 在 NODE_4 和 NODE_16 中，它们将 4 到 16 个 8 位 key 放在节点的第一部分。搜索 key 的成本是 32 位和 128 位，可以装入常规寄存器和 SIMD 寄存器。

但是，如果我们在 NODE_48 中使用相同的方式，搜索的成本是读取 384 位，这甚至无法放入 256 位 SIMD 寄存器。所以，Viktor Leis 等人。在 NODE_48 的第一部分使用子索引而不是键。子索引包含 256 个 8 位偏移量，表示指针的位置。例如。如果要在 NODE_48 中搜索 103(可以是 0 到 255)，程序将:

1. 跳转到子索引的第103个槽位(从0开始)
2. 从第 103 个槽读取值并假设它是 5
3. 跳转到子指针中的第5个槽位
4. 从第5个槽读取指针值并转到下一个节点

它执行 2 次偏移计算而不是 48 (SIMD) 选择。

添加:

访问 NODE_4(或 NODE_16)中的第 103 个元素:

1. 读取 NODE 的“key”部分，其中有 4 个键(或 NODE_16 中的 16 个)代表子指针的键。
2. 执行 SIMD 指令以将 103 与所有 4 个键进行比较。
3. 如果其中一个键(比如说第 3 个键)是 103，则跟随第 3 个子指针
4. 如果没有一个key是103，返回not found。