How to work optimally with relational databases
Milap Neupane
1.2K4

I think you should read ‘use the index luke’. It’s comprehensive, and goes into detail about how indexes work for the various DBs and their shape. In particular, indexes are a combination of BSTs and linked lists.