⏭️ Skipping into Easter

Table of Contents

Gm friends! It’s been a while 👀

After some social pressure and a spurt of motivation - we are back!

Welcome to the newsletter. 🎉

Skip Lists 🧐
#

The current Bradfield CSI module is ‘Data Structures for Storage and Retrieval’. In this module, we are looking at key/value databases, and the data structures used within them. Broadly, we want to have two main functions, Get and Put.

We started by asking how you would structure a basic in-memory database.

There are many ways you could do this, but one solution is to store the key/value pairs in a sorted linked list. There are a few issues with this.

The main one: it’s kinda slow.

To find a key, we need to traverse half of the entire elements on average. Same when we ‘put’ a new key into the sorted list.

So, to solve this slowness, we use what is known as a Skip List. (Original Skip List Paper).

A skip list is essentially a multi-level linked list. Each element exists on the lowest level, less on the second level, even less on the third and so on.

When we want to do a Get or a Put, we first search through the highest level. If we can’t find the key we need, we drop down a level and continue our search there. This then progresses until we find our desired key.

By using the multiple levels, we can traverse through the sorted list more quickly.

Consider if we have 8 elements. We may have 8 on the lowest level L1, 4 on L2, and 2 on L3. Then, when searching for a key, we can start on L3 and effectively skip half of the list when searching.

How does this work when we keep adding keys? Do we need to keep rebalancing the list? It turns out, no we don’t.

The level that a key goes up to is decided by probability. Essentially a coin flip takes place, and if we flip heads, the key gets added to the above level. Four heads in a row means the key is on every level until level four!

In this way, the list is essentially self-balancing. Pretty interesting stuff.

This data structure is used in Redis, LevelDB and probably some other databases.

Wikipedia, in case you are curious.

In case I didn’t explain it well, here is an interactive visualisation.

Mojo 🔥
#

An exciting programming language! This week the team open-sourced the standard library. It’s a step in the right direction, but many of us are still waiting for the holy grail - the compiler.

Mojo was on Hacker News this week.

Mojo is a programming language that is meant to be a superset of Python. It promises the easy syntax of Python with the speed of Rust.

Recently the team presented the high-level details. I found this presentation quite interesting.