In this final article of the series, Pawe³ will extend the basic database to support tree-structured data storage. LhimkDB layers, the tree structure functionality can be used as an independent component, and adding it does not preclude the use of LhimkDB as a key-value database. The author will emphasis that the database development is easy and nice.

Three issues ago I started a series of articles on developing a custom database system. Just to remind you, so far we've built an embedded key-value database. In this final article of the series we will extend the basic database to support tree-structured data storage. As with the remaining LhimkDB layers, the tree structure functionality can be used as an independent component, and adding it does not preclude the use of LhimkDB as a key-value database.

LhimkDB is developed in a language of my devising called Lhimk. It is so similar to C/C++ that there is little point in learning it separately, let alone writing tutorials for it. Any language features found in Lhimk and not found in C/C++ are described in the inset Lhimk or within the article itself. Anyone who doesn't fancy using Lhimk (which I can well understand) can very easily rewrite all Lhimk code in C++. Lhimk code can also be linked to from within C/C++ code.

The Datum class

Before we set about implementing the actual tree structure, we need to add one simple and unexciting yet indispensable feature: the ability to store arbitrary data types in the database. The smallest piece of data that can be stored in a database is by convention simply called a datum. The Datum type in Lhimk type is similar to the Variant type found in high-level languages and some object-oriented libraries. There's nothing magical about it - a Datum object simply stores some data with a type identifier and provides a routine for serialising the data to a byte stream to be stored in the database. Serialisation is trivial for primitive types and strings, but for classes things get a bit more complicated. Fortunately, Lhimk provides a dynamic compilation environment, so we can store a class name and later use it to recreate an object by calling the special constructor method deserialize(). An Lhimk class name is also the URL where the source code for the class can be found, so even if we're loading someone else's database and don't have the classes stored in it, Lhimk can dynamically load and compile the relevant classes at runtime.

The Datum class has one more function: it allows generic programming. Let's examine an example. Whenever we store a key-value pair in the database, we need to make calls similar to:

key->serialize(stream);

value->serialize(stream);

Note that we don't know the actual types of key and value. If we could assume they are always class types, there would be no problem - we'd simply need to require classes to implement the serialize() method. Unfortunately, this need not be the case. In C++, the problem is solved by defining specialised methods, so typical C++ code for the above would be:

stream->serialize(key);

stream->serialize(value);

In the Stream class we would then define multiple versions of the serialize() method, specialised to cater for various argument types:

void serialize(int val);

void serialize(float val);

...

The theory is that the compiler should pick the right version for the type of argument passed. In practice, however, type conversion rules in C++ are fairly complex, and if you add to that implicit class conversion operators, it is all to easy to write even a short C++ program that is completely illegible. Using these techniques for larger projects is simply out of the question.

Being aware of these caveats, I obviously wanted to avoid implementing method specialisation (also called parametric polymorphism or multi-methods) in Lhimk. I also had another reason to avoid it: ensuring maximum compilation speed, which is especially important in environments with dynamic source code compilation at runtime. The solution implemented in Lhimk is to use the # operator to write generic code. For example, the #s operator converts its operand to a string, so we can write:

string = "Number: " + 100#s + " value: " + 11.22#s;

However, we can also write:

string = "Number: " + count#s + " value: " + value#s;

regardless of the actual types of count and value. For primitive types, the conversion is handled directly by the compiler, while for class types the operator_hash_s() method is called.

By the same token, we can convert any value (regardless of type) to a Datum using the #d operator. The code for serialising key-value pairs is now:

key#d->serialize(stream);

value#d->serialize(stream);

and the serialize() method is implemented just once, in the Datum class. Now we can store arbitrary values in the database:

@\lds\SkipList[Datum* T][Datum* K]* list =

\lds\SkipList[Datum* T][Datum* K]::new("SKIPDB", 1);

list->beginTransaction();

list[[10#d]] = "abcd"#d;

list->commitTransaction();

Tree structure part 1

A database element can store any data type, so if we store a list of elements, we will have a tree. The actual tree structure implementation comes almost for free - a bonus for using generic programming and the Datum type. I honestly spent two weeks thinking about it and finally sat down and wrote it in an hour. Natural though it was, the solution initially just seemed too trivial for a production application (see Figure 1). However, before we set about implementing tree structure, we need to add another vital database construct: user transactions.

Figure 1. Building a tree using the Datum type and lists

sum:

0 €

» Library of the Month
» Workshop
» Software Engineering
» Programming Tools
» Interview
» High quality and
secure programming
» Reverse Engineering
» Portable GUI
» Artificial intelligence