This post is about implementing secondary indexes on top of an
ordered key-value store. This topic is interesting for at least
two reasons. First, you may actually need to do this if you’re
implementing secondary indexes on top of something like LevelDB,
RocksDB, Bolt, or some other key-value storage library. Second,
seeing how this is done from an implementation perspective can
help you understand how databases like MySQL and PostgreSQL
handle secondary indexes.
Suppose we have a table implemented on top of a key-value store.
Specifically, assume that the key-value store has unique, ordered
Here’s the row definition:
Row := (id, username, email, deleted timestamp, name)
There are five columns. We’ll let
id be the primary
key. There’s a
deleted column to allow usernames to
be reused. More on that later.
Here’s what the table would look like when …[Read more]