4

ディスクベースの B+ ツリー実装を提供するライブラリはありますか? すべてのキーが固定サイズで、すべての値も固定サイズ (キーと同じ固定サイズであるとは限りません) のシナリオ向けに特別に設計されていますか?

注:はい、もう 1 つの玩具で概念実証用の RDBMS を実装したいと考えています。そして、私が 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;
}
4

2 に答える 2