A library that provides an embeddable, persistent key-value store for fast storage.
C++ Java Perl C Makefile Shell Other
Pull request Compare This branch is 46 commits ahead, 180 commits behind facebook:master.
Latest commit f4859ce Feb 17, 2017 @vmx Refactor into `NextIfDisjoint()`
This is not a functional change, it's just a refactoring into one
common function.
Permalink
Failed to load latest commit information.
arcanist_util Rocksdb contruns to new Sandcastle API Nov 10, 2016
build_tools
cmake/modules
coverage
db
docs
examples
hdfs
include/rocksdb
java
memtable
port
table
third-party
tools Add db_bench option for stderr logging Dec 10, 2016
util
utilities Fix compile error in trasaction_lock_mgr.cc Dec 6, 2016
.arcconfig
.clang-format
.gitignore
.travis.yml
AUTHORS Add AUTHORS file. Fix #203 Sep 29, 2014
CMakeLists.txt Kill flashcache code in RocksDB Dec 1, 2016
CONTRIBUTING.md
DEFAULT_OPTIONS_HISTORY.md
DUMP_FORMAT.md
HISTORY.md
INSTALL.md Update documentation to point at gcc 4.8 Oct 29, 2016
LANGUAGE-BINDINGS.md
LICENSE
Makefile
PATENTS
README.md
ROCKSDB_LITE.md
USERS.md
Vagrantfile
WINDOWS_PORT.md
appveyor.yml fix vs generator (#1269) Aug 10, 2016
src.mk
thirdparty.inc

README.md

rtree-table fork of RocksDB

Overview

This is an experimental fork of RocksDB which implements and R-tree. This enables you to do multi-dimensional queries. At the moment only bounding boxes with floating point numbers (doubles) are accepted as input.

Current state

The code isn't heavily tested or optimised yet, its release follows the “release early, release often” paradigm. Pull requests are welcome.

Goals

The goal is to make this fork obsolete and make the code work with a vanilla RocksDB. Until this is achieved, I'll try to keep the code changes to the original source as minimal as possible (diff of all my changes).

Implementation

The current implementation consists of a custom Table format implementing the R-tree and custom Memtable that is based on the SkipList based one.

The R-tree is ordered by the low value of the first dimension. This minimises the changes that need to be done on RocksDB as it expects a total order of the keys. This also leads to the nice property of having the results always sorted the same way. The idea is based on the paper On Support of Ordering in Multidimensional Data Structures by Filip Křižka, Michal Krátký, Radim Bača.

The Memtable is just RocksDB's default SkipList where there not matching bounding boxes are filtered out dynamically on query time.

The API

No special API is needed, the existing RocksDB API is re-used.

Setup

The include files that are needed for the API section are:

#include <iostream>

#include "db/memtable.h"
#include "rocksdb/db.h"
#include "rocksdb/table.h"
#include "table/rtree_table_util.h"

For using the R-tree you need to define the custom Table, Memtable and comparator:

rocksdb::Options options;
rocksdb::RtreeTableOptions table_options;
table_options.dimensions = 2;
options.table_factory.reset(rocksdb::NewRtreeTableFactory(table_options));
options.memtable_factory.reset(new rocksdb::SkipListMbbFactory);
options.comparator = rocksdb::LowxComparator();

Adding data

Opening a database is just the same as with a vanilla RocksDB:

rocksdb::DB* raw_db;
std::unique_ptr<rocksdb::DB> db;
options.create_if_missing = true;
rocksdb::Status status = rocksdb::DB::Open(options, "/tmp/rtreetable", &raw_db);
db.reset(raw_db);

The data that is inserted are multi-dimensional bounding boxes. This means you have a low and a high value for every dimension. Currently only doubles are supported. Your code may look like this:

std::vector<double> augsburg_key = {10.75, 11.11, 48.24, 48.50};
rocksdb::Slice augsburg_slice = rocksdb::Slice(reinterpret_cast<const char*>(
    augsburg_key.data()), sizeof(augsburg_key[0]) * augsburg_key.size());
status = raw_db->Put(rocksdb::WriteOptions(), augsburg_slice, "augsburg");
std::vector<double> alameda_key = {-122.34, -122.22, 37.71, 37.80};
rocksdb::Slice alameda_slice = rocksdb::Slice(reinterpret_cast<const char*>(
    alameda_key.data()), sizeof(alameda_key[0]) * alameda_key.size());
status = db->Put(rocksdb::WriteOptions(), alameda_slice, "alameda");

Querying the data

Creating and iterator is the same as with a vanilla RocksDB:

std::unique_ptr <rocksdb::Iterator> it(db->NewIterator(rocksdb::ReadOptions()));

The bounding box you want to query on is specified by Seek():

std::vector<double> query = {10, 11, 48, 49};
rocksdb::Slice query_slice = rocksdb::Slice(reinterpret_cast<const char*>(
    query.data()), sizeof(query[0]) * query.size());
it->Seek(query_slice);

Iterating over the results is again the same as the vanilla RocksDB. This prints out the values of the bounding boxes that intersect with the window query as specified by Seek().

for (; it->Valid(); it->Next()) {
    std::cout << it->value().ToString() << std::endl;
}

Full example

A full example can be found in examples/rtree_example.cc. You can build it with

make static_lib
cd examples
make rtree_example

The executable is located in the examples directory.

The original Readme

RocksDB: A Persistent Key-Value Store for Flash and RAM Storage

Build Status Build status

RocksDB is developed and maintained by Facebook Database Engineering Team. It is built on earlier work on LevelDB by Sanjay Ghemawat (sanjay@google.com) and Jeff Dean (jeff@google.com)

This code is a library that forms the core building block for a fast key value server, especially suited for storing data on flash drives. It has a Log-Structured-Merge-Database (LSM) design with flexible tradeoffs between Write-Amplification-Factor (WAF), Read-Amplification-Factor (RAF) and Space-Amplification-Factor (SAF). It has multi-threaded compactions, making it specially suitable for storing multiple terabytes of data in a single database.

Start with example usage here: https://github.com/facebook/rocksdb/tree/master/examples

See the github wiki for more explanation.

The public interface is in include/. Callers should not include or rely on the details of any other header files in this package. Those internal APIs may be changed without warning.

Design discussions are conducted in https://www.facebook.com/groups/rocksdb.dev/