lecture: An R-tree index for RocksDB
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