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

  • This video by Tim Chapman goes pretty in depth on indexes and shows a lot of the internal structures. It may be what you are after? Long watch, but totally worth it, even if it doesn't answer your question. – Shaulinator Jul 1 '18 at 18:40

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.