an R-Tree library for Go



A library for efficiently storing and querying spatial data in the Go programming language.

Build Status Go Report Card GoDoc


The R-tree is a popular data structure for efficiently storing and querying spatial objects; one common use is implementing geospatial indexes in database management systems. Both bounding-box queries and k-nearest-neighbor queries are supported.

R-trees are balanced, so maximum tree height is guaranteed to be logarithmic in the number of entries; however, good worst-case performance is not guaranteed. Instead, a number of rebalancing heuristics are applied that perform well in practice. For more details please refer to the references.

This implementation handles the general N-dimensional case; for a more efficient implementation for the 3-dimensional case, see Patrick Higgins' fork.

Getting Started

Get the source code from GitHub or, with Go 1 installed, run go get

Make sure you import in your Go source files.


Storing, updating, and deleting objects

To create a new tree, specify the number of spatial dimensions and the minimum and maximum branching factor:

rt := rtreego.NewTree(2, 25, 50)

You can also bulk-load the tree when creating it by passing the objects as a parameter.

rt := rtreego.NewTree(2, 25, 50, objects...)

Any type that implements the Spatial interface can be stored in the tree:

type Spatial interface {
  Bounds() *Rect

Rects are data structures for representing spatial objects, while Points represent spatial locations. Creating Points is easy--they're just slices of float64s:

p1 := rtreego.Point{0.4, 0.5}
p2 := rtreego.Point{6.2, -3.4}

To create a Rect, specify a location and the lengths of the sides:

r1, _ := rtreego.NewRect(p1, []float64{1, 2})
r2, _ := rtreego.NewRect(p2, []float64{1.7, 2.7})

To demonstrate, let's create and store some test data.

type Thing struct {
  where *Rect
  name string

func (t *Thing) Bounds() *Rect {
  return t.where

rt.Insert(&Thing{r1, "foo"})
rt.Insert(&Thing{r2, "bar"})

size := rt.Size() // returns 2

We can insert and delete objects from the tree in any order.

// do some stuff...

Note that Delete function does the equality comparison by comparing the memory addresses of the objects. If you do not have a pointer to the original object anymore, you can define a custom comparator.

type Comparator func(obj1, obj2 Spatial) (equal bool)

You can use a custom comparator with DeleteWithComparator function.

cmp := func(obj1, obj2 Spatial) bool {
  sp1 := obj1.(*IDRect)
  sp2 := obj2.(*IDRect)

  return sp1.ID == sp2.ID

rt.DeleteWithComparator(obj, cmp)

If you want to store points instead of rectangles, you can easily convert a point into a rectangle using the ToRect method:

var tol = 0.01

type Somewhere struct {
  location rtreego.Point
  name string
  wormhole chan int

func (s *Somewhere) Bounds() *Rect {
  // define the bounds of s to be a rectangle centered at s.location
  // with side lengths 2 * tol:
  return s.location.ToRect(tol)

rt.Insert(&Somewhere{rtreego.Point{0, 0}, "Someplace", nil})

If you want to update the location of an object, you must delete it, update it, and re-insert. Just modifying the object so that the *Rect returned by Location() changes, without deleting and re-inserting the object, will corrupt the tree.


Bounding-box and k-nearest-neighbors queries are supported.

Bounding-box queries require a search *Rect. It returns all objects that touch the search rectangle.

bb, _ := rtreego.NewRect(rtreego.Point{1.7, -3.4}, []float64{3.2, 1.9})

// Get a slice of the objects in rt that intersect bb:
results := rt.SearchIntersect(bb)


You can filter out values during searches by implementing Filter functions.

type Filter func(results []Spatial, object Spatial) (refuse, abort bool)

A filter for limiting results by result count is included in the package for backwards compatibility.

// maximum of three results will be returned
tree.SearchIntersect(bb, LimitFilter(3))

Nearest-neighbor queries find the objects in a tree closest to a specified query point.

q := rtreego.Point{6.5, -2.47}
k := 5

// Get a slice of the k objects in rt closest to q:
results = rt.NearestNeighbors(k, q)

More information

See GoDoc for full API documentation.



Written by Daniel Connelly ([email protected]).


rtreego is released under a BSD-style license, described in the LICENSE file.

  • NearestNeighbors not returning correct point

    NearestNeighbors not returning correct point


    Thanks for this awesome lib. I am facing an issue : I have following points: keysBody := []byte([{"id": "1","name": "A","location": [88.495873,22.551802]},{"id": "2","name": "B","location": [88.490197,22.552743]},{"id": "3","name": "C","location": [88.492724,22.558270]}]) ................. type Storage struct { Users map[string][]*user geoIndex *rtreego.Rtree nearestNeighbors int } ............. geoIndex.Insert(user) ............ lat := 22.562454 lon := 88.494374 ... geoIndex.NearestNeighbors( 20, rtreego.Point{lat, lon}, )

    It always return : {"id": "2","name": "B","location": [88.490197,22.552743]} while id 3 (name c) is nearest

    am I doing wrong or something ?

    opened by tamal-appsbee 6
  • Search result filtering

    Search result filtering

    Adds support for filtering results of the search. Addresses a use case where I want to search for objects in the tree in a specified area with specified characteristics with a specified amount of results. Doing the filtering while searching prevents problems like asking for 100 results but after filtering the returned results, only having 45 viable results at hand.

    Also removes documentation about SearchContained function which seems to be missing.

    opened by SamiHiltunen 4
  • make plain Rect struct instead of pointer

    make plain Rect struct instead of pointer

    This is to improve performance by avoiding garbage collection. As shown in the pprof graphs to be uploaded in the pull request, before this change the time spent in GC is:

    runtime.mallocgc 18.19% runtime.scanobject 25.23%

    which adds up to almost half the running time.

    before before.pb.gz

    After this change, the time spent is:

    runtime.mallocgc 7.08% runtime.scanobject 6.40%

    which is a significant reduction.

    after after.pb.gz

    This remaining time wasted in GC can be further shaved off if Point is defined with fixed sized arrays, instead of slices. However, fixed sized arrays run counter to the aspirations of this library so it is not pursued here.

    opened by fumin 3
  • PR Add Feature to Retrieve Non-Leaf Bounding Boxes

    PR Add Feature to Retrieve Non-Leaf Bounding Boxes

    Would you consider accepting this PR which adds functionality to get the bounding boxes of all non-leaf nodes? This is useful for visualizations of the tree and analyzing resulting clusters of data. I have implemented the feature and tests on PR.

    This change introduces one public method GetAllBoundingBox on Rtree which calls getAllBoundingBox. getAllBoundingBox traverses the tree from root building a slice of non-leaf bounding boxes and returns it.

    opened by cbergoon 3
  • NearestNeighbors filters & OMT bulk-loading

    NearestNeighbors filters & OMT bulk-loading


    This pull request adds two things:

    1. Filtering for NearestNeighbors searches
    2. Overlap Minimizing Top-down bulk-loading

    I tested the bulk-loading on a small dataset of 50000 objects by querying 200 objects. It lowered both the tree building and the search times to 1/6th.

    PR is a bit on the large side, if you have any questions, let me know.

    opened by SamiHiltunen 3
  • NewRectFromPoints should not modify its inputs

    NewRectFromPoints should not modify its inputs

    NewRectFromPoints currently modifies its input slices without any warning in the documentation to the caller.

    This can result in hours of troubleshooting, as it only happens if some first coordinate is above the second coordinate.

    Also consider using value types (arrays) instead of reference types (slices).

    opened by magnushiie 2
  • optimize condenseTree and computeBoundingBox

    optimize condenseTree and computeBoundingBox

    condenseTree contains memory allocations that when triggered causes the following time spent:

    runtime.mheap.alloc 39.27%


    Similarly, particular Delete heavy workloads might trigger unnecessary

    computeBoundingBox 16.57%


    This change fixes these performance issues.


    opened by fumin 2
  • Invalid data in tree after Inserting

    Invalid data in tree after Inserting

    I think there is a bug. I tried bulk load, then deleting every 2nd element, and inserting back all elements deleted. After that there are several copies of some elements and some are missing.

    I managed to find out, that this append sometimes changes entities in at least 2 nodes. I think it is somehow connected with the thing that several slices can point to same array

    opened by codpe 2
  • Break filter loop on first refuse

    Break filter loop on first refuse

    This PR resolves #22. We are running this in production and it greatly improved the performance of our searches by placing more expensive filters at the end of the list of filters.

    opened by db7 2
  • NearestNeighbors prunes too much

    NearestNeighbors prunes too much

    The current implementation of NearestNeighbors is pruning too early branches. That results in incorrect searches. For example, if the tree contains N entries and one searches for N entries, the search will return less than N, although it would have enough entries to fulfill the request.

    This pull request introduces 3 main changes to the prune strategy. The search prunes

    • the branches based on the furthest node in the buffer (dists and nearest)
    • using minDist instead of minMaxDist and
    • only after k nodes are in the buffer.

    This approach follows what is actually described here in Enhanced Nearest Neighbour Search on the R-tree.

    The PR also changes the NearestNeighbors test case to reveal the issue above and does some performance improvement in insertNearest by removing unnecessary allocations.

    opened by db7 2
  • will you implement R*tree?

    will you implement R*tree?

    R*Tree has better query performance.

    I'm going to use RTree to do multi-dimension information query, instead of for spatial searching, for example, to query records witch satisfies [type, age, score... etc... ], I think rtree fits well for this situation.

    opened by xtaci 2
  • Why you only do slice on top level?

    Why you only do slice on top level?

    Hi, I noticed that in the r-tree implementation where in file "rtree.go", you only do the slicing at the root level, the other levels use just one slice whose length is the size of entire current subdataset (i.e. don't slice).

    May i ask why you are doing this?

    From what I have observed, if the slicing strategy is used in every height of recursion, it is possible to generate better leaf MBRs (their length and width are closer rather than one being much larger than the other).

    opened by Isuxiz 1
  • Picking numbers for Min/MaxChildren

    Picking numbers for Min/MaxChildren

    Firstly, thanks for the library, really helpful.

    I'm dealing with a set of documents that ranges from 10 points to 100,000 points. Each document has its own rtree and I'd be interested in "intelligently" picking the min/max children for each tree I generate.

    Could you offer some advice about how I should go about picking appropriate min/max children?


    opened by hcliff 1
  • Ouput an image for debugging

    Ouput an image for debugging

    We are using your project in a non-graphical context and we are still in the developement phase. For the sake of debugging we would like to know the current state of the rtree.

    Many libraries for Quadtree can ouput a PNG with all the points and regions.

    There is a String method but it only returns "foo" instead of a string representation of the rtree.

    opened by xtuc 2
  • Encode/Decode using gob.

    Encode/Decode using gob.

    Hello I am using your library in one of the projects and it would be nice if you can help me out with using gob package to pack/unpack RTree.

    We parse a lot of data from XML to RTree and this data is not changing after server start. Good way will be to load it back from file (using gob encode/decode).

    Thank you.

    opened by m1ome 5
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 19 Mar 17, 2022
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

Cameron Bergoon 406 Jan 5, 2023
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to if you encounter breaking changes. Motivation Introduction Us

Viant, Inc 31 Nov 3, 2022
AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

Michael Lore 28 Mar 23, 2022
An yet-another red-black tree implementation, with a C++ STL-like API.

A red-black tree with an API similar to C++ STL's. INSTALLATION go get EXAMPLE More examples can be fou

Yasushi Saito 18 Apr 25, 2022
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Josh Baker 236 Dec 29, 2022
Just an itsy bitsy b-tree in Go

tinybtree Just an itsy bitsy b-tree. Usage Keys are strings, values are interfaces. Functions Get(key string) (value interface{}, gotten bool) Set(key

Josh Baker 93 Dec 25, 2022
An immutable radix tree implementation in Golang

go-immutable-radix Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimi

HashiCorp 859 Dec 29, 2022
B-tree implementation for Go

btree btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (<500LOC) and highly do

Amit Davidson 214 Dec 31, 2022
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

null 4 Mar 7, 2022
Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Arun Shaji 3 Oct 6, 2021
Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

Arthur Abeilice 0 May 17, 2022
Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

web_developer 1 Oct 9, 2021
Segment tree for bytes in Go

bsegtree Segment tree for bytes in Go Based on Thomas Oberndörfer's int range segment tree with fixing/optimization/modification for bytes ranges. For

Temple3x 3 Jun 16, 2022
A project that deals with implementations of a binary tree

Binary Search Tree This is a project that deals with implementations of a binary tree and the following functions. Print Prints the entire tree. Argum

Victor Zeddys 1 Nov 1, 2021
A versioned, snapshottable (immutable) AVL+ tree for persistent data.

IAVL+ Tree Note: Requires Go 1.13+ A versioned, snapshottable (immutable) AVL+ tree for persistent data. The purpose of this data structure is to prov

null 0 Nov 24, 2021
publish a tree-like data structure from a backend to a front-end

tree-publish publish a tree-like data structure from a backend to a front-end. It needs to be a tree in order to publish the data as JSON document. If

Lutz Behnke 0 Dec 20, 2021
Mmpxmas-go - ModMyPi Programmable Christmas Tree examples written in Go with go-rpio

ModMyPi Programmable Christmas Tree examples in Go This small program contains examples similar to the examples provided by ModMyPi for interacting wi

Tyler Darnell 0 Jan 4, 2022
watch for file changes (matching a suffix whitelist) in a directory tree and run a command when they change

watchspawn what is it? Watches for file creates and writes in and below the current directory and when any of them (matching a suffix list) change, ru

John Slee 0 Jan 16, 2022