Как создать простой индекс префикса в Java?

У меня большой набор URL-адресов, и я хочу реализовать автодополнение. Мне не нравится сложность наивного подхода, поскольку он линейен с размером набора:

for(String url: urls) if(url.startsWith(input) {doSomething();}

Теперь я знаю, что в наборе хэшей функция «содержит()» работает в «O( 1)», но нет «containsPrefix()». Есть ли простой способ без использования большой библиотеки, такой как Lucene, или без ее кодирования? У меня не было бы проблем с этим, но это кажется излишним для такой простой проблемы, поэтому я хочу знать, существует ли существующее простое решение :-)

Из моих уроков информатики я помню дерево, которое состоит из строковых фрагментов, но я забыл, как оно называлось. Это работало так:

[car, care, carrot,carrotville]->

car
|
-/
-e
-rrot
  |
  ----ville

P.S.: Как вызвать методы, которые возвращают все строки, префиксом которых является строка? Например, если a является префиксом b, что такое b для a?