lmdb is just k/v, so the index would be: k: uid v: varint-partitioned-array of people they follow You could do a composite key: k: (uid, uid) -> user, follow but that would be horribly space inefficient yes all of our indices are hand rolled and optimized for space

Yes, it thoguht there was a name for these types of indexing data structures. I remember seeing something like that (you just store the array itself as varints) in school. That's why id locality was (maybe still is) such a big deal back in the day. I remember a paper that discussed those two alternatives in the light of write and read speeds and you would choose them based on your system being write or read centric. We even did a server mirroring setup one day on the old Oracle with one server to receive data with a write index and 3 others were read-only and using the read index. That was the first time I understood that sometimes the best option is all of them :)