4 releases

Uses old Rust 2015

0.1.3 Jun 24, 2016
0.1.2 Jun 23, 2016
0.1.1 Apr 19, 2016
0.1.0 Apr 19, 2016

#6 in #gist


755 lines

Gist - Generalised Search Tree

A Generalised Search Tree is a tree structure similar to B+Trees that has a key structure that has been abstracted to an interface. This allows it to be used for various interesting structures like B+Trees, RTrees, BallTrees, and so on, just by inmplementing the interface for the GstKey. GiSTs were made popular by Postgres since they allow people to make interesting indices on tables that efficiently handle things like time intervals, or PostGIS.

This is a work in progress so there are some bits of weirdness.

e.g. It only handles Rects which then have Rects as the keys rather than having Rects in intermediate nodes which are pointing to Points or whatever.

Also, removal is a bit shonky and empty leaves are left in the tree. But to be fair, the original libgist has this issue too.

h2. Naming The name gist was taken just four days before I tried uploading this to Crates.io by a project for uploading Github gists. No one seems to know what the 'i' in GiST stands for anyway.


~31K SLoC