Limousine

limousine 是对混合键值存储世界的探索。传统的索引（如B树）经过几十年的优化，为插入和读取提供了持续的性能。另一方面，利用统计模型来近似键位置的机器学习索引，在内存使用和读取性能方面带来了巨大好处。然而，这些新的结构也带来了一些权衡；最显著的是，没有标准或高效的算法来执行插入。

本项目实验了混合键值存储——由传统的B树节点和机器学习统计模型节点组合而成的数据结构。目标是利用这两种索引方法的优点，同时提高机器学习索引插入的先进水平。虽然开发高效可变的混合索引是研究的热点，但这个crate提供了一个完全功能的原型，可以将布局规范转换为工作设计。

我们的大部分机器学习索引工作受到了PGM索引的启发。

这是一个主要原型项目。虽然生成的键值存储是功能性的并且相当高效，但它们缺少许多功能，如高效删除条目、批量插入、多线程插入、事务等。最终，我们希望实现这些功能，但是与动态代码生成新型数据结构相关的挑战多种多样，这仍然是一个活跃的研究领域。

概述

limousine_engine 提供了一个过程宏，用于自动生成由经典和机器学习组件组成的混合键值存储设计。

截至当前版本，机器学习组件尚不支持。

use limousine_engine::prelude::*;

create_kv_store! {
    name: ExampleStore,
    layout: [
        btree_top(),
        pgm(epsilon = 8),
        pgm(epsilon = 8),
        btree(fanout = 32),
        btree(fanout = 32, persist),
        btree(fanout = 64, persist)   
    ]
}

要生成设计，我们提供一个结构名称和布局描述，该描述由组件堆栈组成。例如，在上面的示例中，键值存储由一层磁盘上的B树节点组成，其分支因子为64，下面是
一层磁盘上的B树节点，分支因子为32，下面是内存中的B树节点层，分支因子为32。在这之上，我们有两个内存中的PGM学习层，epsilon参数为8，以及一个作为顶层的小型内存B树。

由于尚未完全支持已学习的组件，上面的示例无法编译。要在当前版本中获得可工作的键值存储，我们应该仅使用BTree组件。

use limousine_engine::prelude::*;

create_kv_store! {
    name: ExampleStore,
    layout: [
        btree_top(),
        btree(fanout = 8),
        btree(fanout = 8),
        btree(fanout = 32),
        btree(fanout = 32, persist),
        btree(fanout = 64, persist)   
    ]
}

然后我们可以使用这些生成数据结构来执行查询

// Load the first two layer of the index from memory
let index: ExampleStore<u128, u128> = ExampleStore::open("data/index")?;

index.insert(10, 50)?;
index.insert(20, 60)?;
index.insert(30, 70)?;
index.insert(40, 80)?;

assert_eq!(index.search(10)?, Some(50));