Всегда ли индекс является деревом

Нет, не всегда. В Java индексы в базах данных могут быть реализованы разными структурами, включая B-деревья (наиболее распространены), хеш-индексы, битовые индексы и другие. Например, в MySQL InnoDB по умолчанию использует B+ деревья, а для MEMORY таблиц можно выбрать хеш-индекс:

CREATE TABLE test (
    id INT PRIMARY KEY,
    name VARCHAR(100)
) ENGINE=MEMORY DEFAULT CHARSET=utf8 
  COMMENT='Хеш-индекс по умолчанию';

Выбор структуры зависит от СУБД и конкретного типа индекса. B-деревья хороши для диапазонных запросов, а хеши - для точечного доступа.