Базы данных могут использовать различные структуры данных для индексации, но чаще всего наверно можно увидеть B-Tree, B+Tree и Hash. Hash достаточно популярный, потому что используется не только в базе данных. Деревья распространены, но не так сильно.
В этом видео я поговорю в теории о индексах. Это не конкретная реализация какой-то базы, а общая теория.
Дядя Миша круто рассказал и он профи, друзья мои.