What data structure is used for MongoDB 3.x geospatial indexes?

Posted on

Question :

For the MongoDB 3.x geospatial features what structure is used for the indexes? B-tree? R-tree? X-tree? I can’t find any information about the structures in their documentation

Answer :

The general index format used by MongoDB’s included storage engines as at 3.0.x (MMAPv1 and WiredTiger) is B-tree, however there are more nuances in the technical implementation.

MongoDB 3.0 introduced a storage engine API which separates the concerns of storage formats (i.e. data & index representations on disk and in memory) from the core server product. For example, WiredTiger supports index prefix compression, data compression, and more granular concurrency than MMAPv1.

It is expected that alternative storage engine implementations can (and will) differ in their underlying implementation of indexes and data storage to suit different workloads. For example, WiredTiger has support for LSM (Log Structured Merge-Trees) which is expected to be available in the MongoDB 3.2 production release. There are also alternative storage engines such as RocksDB (which uses LSM) and TokuMXse (which uses Tokutek’s fractal tree storage).

I’m not aware of any pluggable storage engines for MongoDB that have been specifically optimized for storage of spatial data, but it is conceivable that one may be created.

Leave a Reply

Your email address will not be published. Required fields are marked *