database - 具有固定大小键和值的基于磁盘的 B+ 树实现

Question

有没有提供基于磁盘的B+树实现的库，专门针对所有键大小固定，所有值也大小固定(不一定与键固定大小相同)的场景设计的？

注意:是的，我想实现另一个玩具，概念验证 RDBMS。还有 a very good reason为什么我不使用 SQL DBMS。 笔记结束。

我并不特别介意库是用什么语言编写的。但是，我对库的功能有一些特定的要求。为了清楚起见，将使用 C 语言编写的示例来说明这些要求。

库必须足够灵活以允许我使用自己的比较函数。例如:

struct comparer
{
    void * extra;
    int (*function)(
        void *, // closure over extra
        char *, // 1st value to be compared
        char *  // 2nd value to be compared
    );
};

索引文件的操作机制由所有键的固定长度、所有值的固定长度以及键的比较函数定义。例如:

struct index_spec
{
    size_t keylen, vallen;  // fixed lengths for keys and values
    struct comparer comp;   // comparison function for keys
};

如果库在可查询索引和可更新索引之间建立区别，并在预期可查询索引时使用可更新索引的机制，而不是相反，那将是一个非常好的接触(虽然不是强制性的)。例如:

struct queryable_index
{
    struct index_spec spec;
    FILE * file;            // opened in read mode
};

struct updateable_index
{
    struct index_spec spec;
    FILE * file;            // opened in read/write mode
};

struct queryable_index open_queryable_index
    (struct index_spec, const char *);

struct updateable_index open_updateable_index
    (struct index_spec spec, const char * filename);

struct queryable_index just_queryable_index
    (struct updateable_index index)
{
    struct queryable_index result;
    result.spec = index.spec;
    result.file = index.file;
    return result;
}

Answer 1

据我所知，最好的实现是 Berkeley DB .它是一个高性能的嵌入式数据库系统，具有非常好的 B 树实现，由 Sleepycat 开发，后来被 Oracle 收购。

它是用C语言编写的，支持你所追求的使用场景。它是开源的，如果您想构建自己的实现，代码是寻找灵感的好地方。

玩得开心!