Version 0.8

lecture: An R-tree index for RocksDB

Event large 4b8aa978adbb7c8e80151f5a83c6782a12e763374ae3a042a55e7e626a64d93b

This talk is about implementing a R-tree on top of RocksDB, an LSM-tree (log-structured merge-tree) based key-value store. It will give an introduction about how RocksDB works and why LSM-trees are such a perfect fit to build an R-tree index on top of them. Finally there will be a deep dive into the actual R-tree implementation.


RocksDB is a popular key-value store by Facebook (based on Google's LevelDB). It supports key and range lookups and basic spatial indexing based on GeoHash, but not an R-tree implementation which makes multi-dimensional queries possible. Those queries can combine things like location and time, but also any other property that can be represented as a numeric value, such as categories. This makes it possible to query e.g. for all flats with a certain size in a specific area that are not older than a few years and have a balcony.


Links to project: https://github.com/vmx/rocksdb/tree/wip-rtree-index