[jupiter909]

o Fractal Tree Index's are rather nifty as used in Tokudb engine. Basic gist is that you get the speed of Btree but your update are less painful.

https://en.wikipedia.org/wiki/Fractal_tree_index http://www-db.deis.unibo.it/courses/TBD/Lezioni/mysqluc-2010...

o k-d tree for space partitioning, handy real world applications in mapping and gaming.

o Bloom Filters as you mention are great, always a handy one to know.