What actual data structures do you know that can be used for indexing and storage?

Question

Database

I dived into spatial indexing with my head, figured out all sorts of murky cache-obvious lookahead arrays and how to build various spatial, and not very, sometimes fuzzy, indexes from them. I especially liked the work of Michael Bender and Tokutek in this direction, but there are still shortcomings.
Can you please advise interesting data structures that could be used for indexing and storage, perhaps there are some new trends that I managed to miss.
Links to citations and publications are welcome.
Thank you.
ps I don't think B-tree and LSM-tree are relevant.

Answer 1

If B-tree is no longer a cake, read about relaxed B-tree .
Question tags contain relational databases. Tree and hierarchical structures in general are alien to relational algebra, but they are ubiquitous. Researched workaround is Adjacency list and nested sets