R tree index quick start and usage - AnaNek/tarantool GitHub Wiki

R-tree (spatial) index could not be primary, and could not be unique. The 'parts' of rtree index definition must contain the one and only part with type 'array'.

s = box.schema.create_space("test")
i = s:create_index('primary', { type = 'HASH', parts = {1, 'num'} })
r = s:create_index('spatial', { type = 'RTREE', unique = false, parts = {2, 'array'} })

One can set the dimension of R-tree space:

r2 = s:create_index('spatial', { type = 'RTREE', unique = false, dimension = 8, parts = {3, 'array'} })

The default dimension of an R-tree index is 2, that is 2D space. Now dimension if R-tree index is limited by 20. The following spec and examples are presented for 2D case unless otherwise stated.

Corresponding tuple field thus must be an array of 2 or 4 numbers. 2 numbers mean a point {x, y}; 4 numbers mean a rectangle {x1, y1, x2, y2}, where (x1, y1) and (x2, y2) - diagonal point of the rectangle.

s:insert{1, {1, 1}}
s:insert{2, {2, 2, 3, 3}}

Selection results depend on a chosen iterator. The default EQ iterator searches for an exact rectangle (a point is treated as zero width and height rectangle)

r:select{1, 1}
---
- - [1, [1, 1]]
...
r:select{1, 1, 1, 1}
---
- - [1, [1, 1]]
...
r:select{2, 2}
---
- []
...
r:select{2, 2, 3, 3}
---
- - [2, [2, 2, 3, 3]]
...

Iterator ALL (which is the default when no key is specified) selects all tuples in arbitrary order

r:select{}
---
- - [1, [1, 1]]
  - [2, [2, 2, 3, 3]]
...

Iterator LE (less or equal) searches for tuples with their rectangles within a specified rectangle

r:select({1, 1, 2, 2}, {iterator='le'})
---
- - [1, [1, 1]]
...

Iterator LT (less than, or strictly less) searches for tuples with their rectangles strictly within a specified rectangle

r:select({0, 0, 3, 3}, {iterator='lt'})
---
- - [1, [1, 1]]
...

Iterator GE searches for tuples with a specified rectangle within their rectangles

r:select({1, 1}, {iterator='ge'})
---
- - [1, [1, 1]]
...

Iterator GT searches for tuples with a specified rectangle strictly within their rectangles

r:select({2.1, 2.1, 2.9, 2.9}, {itearator='gt'})
---
- []
...

Iterator OVERLAPS searches for tuples with their rectangles overlapping specified rectangle

r:select({0, 0, 10, 2}, {iterator='overlaps'})
---
- - [1, [1, 1]]
  - [2, [2, 2, 3, 3]]
...

Iterator NEIGHBOR searches for all tuples and orders them by distance to the specified point

for i=1,10 do for j=1,10 do s:insert{i*10+j, {i, j, i+1, j+1}} end end
---
...
r:select({1, 1}, {iterator='neighbor', limit=5})
---
- - [11, [1, 1, 2, 2]]
  - [12, [1, 2, 2, 3]]
  - [21, [2, 1, 3, 2]]
  - [22, [2, 2, 3, 3]]
  - [31, [3, 1, 4, 2]]
...

Warning: Don't forget that select NEIGHBOR iterator without limit extract entire space (in order of increasing distance of cause), and that could be tons of data with corresponding performance. And another my favourite mistake is to specify iterator type without quotes, in such way: r:select(rect, {iterator = LE}), and that leads to silent EQ select, 'cause LE is undefined variable and treated as nil, so iterator is unset and default used. So please don't forget quotes.

3D, 4D and more dimensional R-tree indexes works in the same way as 2D except that user must specify more coordinates in requests. Here's short example of using 4D tree:

s = box.schema.create_space('test')
---
...
i = s:create_index('primary', { type = 'HASH', parts = {1, 'num'} })
---
...
r = s:create_index('spatial', { type = 'RTREE', unique = false, dimension = 4, parts = {2, 'array'} })
---
...
s:insert{1, {1, 2, 3, 4}} -- insert 4D point
---
- [1, [1, 2, 3, 4]]
...
s:insert{2, {1, 1, 1, 1, 2, 2, 2, 2}} -- insert 4D box
---
- [2, [1, 1, 1, 1, 2, 2, 2, 2]]
...
r:select{1, 2, 3, 4} -- find exact point
---
- - [1, [1, 2, 3, 4]]
...
r:select({0, 0, 0, 0, 3, 3, 3, 3}, {iterator = 'LE'}) -- select from 4D box
---
- - [2, [1, 1, 1, 1, 2, 2, 2, 2]]
...
r:select({0, 0, 0, 0}, {iterator = 'neighbor'}) -- select neighbours
---
- - [2, [1, 1, 1, 1, 2, 2, 2, 2]]
  - [1, [1, 2, 3, 4]]
...