论文标题
内存搜索树的订单保护密钥压缩
Order-Preserving Key Compression for In-Memory Search Trees
论文作者
论文摘要
我们为内存搜索树提供了高速保护编码器（HOPE）。 Hope是一个基于词典的快速压缩机，在保留命令的同时编码任意键。希望的方法是在细粒度上识别常见的关键模式，并利用熵以使用小词典来达到高压率。我们首先开发一个理论模型，以推理有关订购词典设计的理论。然后，我们使用此模型选择六个代表性压缩方案，并在希望中实现它们。这些方案在压缩率和编码速度之间做出了不同的权衡。我们评估数据库中使用的五个数据结构：冲浪，艺术，热，B+树和前缀B+树。我们的实验表明，对于大多数字符串键工作负载，使用希望允许搜索树达到较低的查询延迟（最多40 \％\％降低）和更好的内存效率（最多30 \％）。
We present the High-speed Order-Preserving Encoder (HOPE) for in-memory search trees. HOPE is a fast dictionary-based compressor that encodes arbitrary keys while preserving their order. HOPE's approach is to identify common key patterns at a fine granularity and exploit the entropy to achieve high compression rates with a small dictionary. We first develop a theoretical model to reason about order-preserving dictionary designs. We then select six representative compression schemes using this model and implement them in HOPE. These schemes make different trade-offs between compression rate and encoding speed. We evaluate HOPE on five data structures used in databases: SuRF, ART, HOT, B+tree, and Prefix B+tree. Our experiments show that using HOPE allows the search trees to achieve lower query latency (up to 40\% lower) and better memory efficiency (up to 30\% smaller) simultaneously for most string key workloads.
