Usually the data structure behind an index is a B-Tree or a variation of it. It sometimes depends on the nature of the data that you are indexing (R-Trees for example are good for spatial data). One good way to figure out how all this works is to start writing your own toy system using something for BerkeleyDB as the index / storage engine if you do not want to implement your own at such a low level.
Yiorgos Adamopoulos
DevOps for Lotteries
Usually the data structure behind an index is a B-Tree or a variation of it. It sometimes depends on the nature of the data that you are indexing (R-Trees for example are good for spatial data). One good way to figure out how all this works is to start writing your own toy system using something for BerkeleyDB as the index / storage engine if you do not want to implement your own at such a low level.
Database Design offers a lot of insight at the low level.
If you really want to know how all this adds up, implement your own B-Tree and a small query language on top of it.