В какой структуре хранится индекс

Индексы в Java обычно хранятся в хэш-таблицах (HashMap, HashSet) или деревьях (TreeMap, TreeSet).

• HashMap: Использует массив Node<K,V>[] (бакетов) с цепочками для коллизий.
• TreeMap: Красно-черное дерево для упорядоченного хранения.

Пример индекса в HashMap:

Map<String, Integer> index = new HashMap<>();
index.put("key1", 1); // Хранится в бакете по хэшу "key1"

Для больших данных или поиска по диапазону (BETWEEN) используют TreeMap или специализированные структуры (например, инвертированные индексы в Lucene).