How to write a simple database engine?

Question

I am interested in learning how a database engine works (i.e. the internals of it). I know most of the basic data structures taught in CS (trees, hash tables, lists, etc.) as well as a pretty good understanding of compiler theory (and have implemented a very simple interpreter) but I don't understand how to go about writing a database engine. How is the data stored internally (i.e. how tables are represented, etc)? How does the engine finds data that it needs? How is data inserted in a way that is fast and efficient?

Answer 1

The metadata and database table schema are stored in another file: the names of the field columns, the size and type of each field column, # of records in the table, size of each record, primary keys, etc.

So when the open command is sent, the engine reads the database table's schema and metadata, so it knows

what the column fields are, what is the size of each record, etc. and begins loading them into memory.

Depending on the query, it will have to sort the records in memory so that the records are listed in the order specified.

Generically you can do a similar thing as follows:

For each table X in your database:

1. stores the record size and # of records in a file called Xmetadataschema.dat
2. stores the actual records in X.dat
3. declares,defines, and implements a function pointer that compares two records from table x; this function takes two void pointers as arguments, by typecasts them into pointers to structure x.

Now when the table is requested, you can load these records into memory and sort them easily using Quicksort which is implemented for you in stdlib.h. You will need to pass the comparison function pointer created in step 3. Otherwise you will have to write your own generic sorting routine.