CODEWITHSUNDEEP
databasedata-structuresrelational-databaseb-tree
isekaijin
isekaijin

Reputation: 19742

Disk-based B+-tree implementation with fixed-size keys and values

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)?

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.

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.

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

Upvotes: 4

Views: 2141

Answers (2)

phbcanada
phbcanada

Reputation: 99

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."

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

Upvotes: 0

Mårten Wikström
Mårten Wikström

Reputation: 11344

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.

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.

Have fun!

Upvotes: 3

Related Questions