How to Store Skip Lists on Disk

Question

I am new to thinking in terms of databases. I have read about how B-trees are stored on disk but I haven't seen an actual implementation or read about how it works for B-trees.

Wondering how one might store Skip Lists on disk. There are many descriptions for storing it with pointers in memory, but I haven't seen anything on disk storage. Wondering what it might look like at a high level (if it's just one big file or many small files, if there are different types of files, etc.).

Answer 1

A DBMS is an implementation of a datamodel - a structure for how data will be represented. The relational model represents data as tables and columns, graph model as nodes and edges, document model as nested key-value pairs. If your objective is to persist a skip list using an existing DBMS you must map its parts to the model's corresponding affordances.

If the objective is to implement this feature within a DBMS you're no longer bound by that DBMS's external model. A simple implementation would be to replace the memory pointers with the corresponding disk pointers (file_id, offset). By careful arrangement random / sequential reads can be optimised.

I remember some of the MySQL clones have implemented this. Their source is available. These would also include BTree implementations.