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

Is there any library providing a disk-based B+-tree implementation, specifically designed for the scenario in which all keys have a fixed size and all values have a fixed size as well (not necessarily the same fixed size as the keys)?

是否有任何库提供基于磁盘的B + -tree实现,专门针对所有键具有固定大小并且所有值都具有固定大小的场景(不一定与键的固定大小相同)?

Note: Yes, I want to implement yet another toy, proof-of-concept RDBMS. And there is a very good reason why I am not using a SQL DBMS. End of note.

注意:是的,我想实现另一个玩具,概念验证RDBMS。我没有使用SQL DBMS是一个很好的理由。结束了。

I do not particularly mind what language the library is written in. However, I do have some specific requirements regarding the library's functionality. For the sake of clarity, these requirements will be illustrated with examples written in C.

我并不特别介意库的编写语言。但是,我对库的功能有一些特定的要求。为了清楚起见,这些要求将用C语言编写。

The library must be flexible enough to allow me to use my own comparison function. For example:

该库必须足够灵活,以允许我使用自己的比较功能。例如:

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

The mechanics of how an index file should be manipulated is defined by the fixed length for all keys, the fixed length for all values, and the comparison function for keys. For example:

应该如何操作索引文件的机制由所有键的固定长度,所有值的固定长度和键的比较函数定义。例如:

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

It would be a really nice touch (though not mandatory) if the library established a difference between queryable and updateable indices, and a mechanism for using an updateable index when a queryable one is expected, but not the other way around. For example:

如果库在可查询索引和可更新索引之间建立了差异,并且在需要可查询索引时使用可更新索引的机制,那将是一个非常好的触摸(尽管不是强制性的),但不是相反。例如:

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;
}

2 个解决方案

#1

The best implementation that I know of is Berkeley DB. It is a high performance embedded database system with very nice B-tree implementations developed by Sleepycat and later acquired by Oracle.

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

It is written in C and supports the usage scenarios you're after. It is open source and the code is a very good place to look for inspiration if you wish to build your own implementation.

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

Have fun!

#2

LevelDB: "The leveldb library provides a persistent key value store. Keys and values are arbitrary byte arrays. The keys are ordered within the key value store according to a user-specified comparator function."

LevelDB:“leveldb库提供持久的键值存储。键和值是任意字节数组。键是根据用户指定的比较器函数在键值存储区内排序的。”

https://github.com/google/leveldb/blob/master/doc/index.md

#1