Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It only takes a minute to sign up.
Sign up to join this community
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.).
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.
