I am building a database engine in C for Linux and I need to implement indexing. Consider a simple double linked list index like this:
struct node_t {
void *prev;
void *next;
long data;
};
For permanent storage I have to convert this structure in disk blocks, like for example:
struct node_on_disk_t {
size_t prev_disk_block;
short prev_disk_offset;
size_t next_disk_block;
short next_disk_offset;
long data;
};
Now, when I insert a record, one entry must be added to the index too. If the index is only few elements I can store it on 1 disk block consistently because the write() of 1 block is atomic. However if the list fills entirely the first block, another block must be added on insert and pointers must be updated on both blocks. But the problem is, only 1 block can be written atomically. So, my question is how to store this kind of structure consistently?
Can this be done without transaction log? Because I could store the description of the operation on another disk block first (sort of transaction log), update the pointers of the index and then remove the description of the operation, but this would have to be done in 3 write()s , too slow