自适应基数树

Question

从1周开始,我发现了一个名为"Adaptive Radix Tree"的感兴趣话题,我发现它是用于在现代硬件架构中专门索引内存的非常有用的技术.

实际上我无法理解第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位密钥.搜索密钥的成本是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. 如果其中一个键(比如第三个键)是103,请按照第3个子指针
4. 如果没有任何键是103,则返回未找到.