Я не знал как правильно назвать но в общем это еще одна тема для холивара.
 
Вобщем читаем тут
http://mabp.kiev.ua/content/2008/05/08/autocache/
и пишем что думаем. а еще лучше оставляйте ссылки на описание какихнибудь классных алгоритмов кэширования которые можно на это натянуть
 

что неужели никто не может ничего лучшего предложить?

CTAPbIu_MABP, еще бы выделить время на прочтение твоего труда...

Но это все было бы очень хорошо если бы наш бэкэнд (я имею ввиду сайт Киевстара) не возвращал только первых 500 найденных записей на каждый запрос

хм.. Киевстара.. знакомый оператор) а ты откуда кстати? а по поводу алгоритма.. уместен вопрос если при выборе одной буквы выбирается 1000000 записей, при уточнении (+1 буква) 10000 записей, и т.д сколько пользователей одновременно смогут обратится к страничке.. и при какой посещаемости хостер пошлёт тебя куда-подальше..
 
что касаемо кеширования - думаю мускль с этим справится сам. не стоит, имхо, заморачиваться.

вот только причём тут жаб-скрипт)?

ghost, он хочет вынести вычисления на клиент часть, чтобы к серваку не обращаться каждый раз.

Используйте не примитивные строки, а объекты String(), тогда элементы массивов будут содержать только ссылки на них.
 
Сначала определите до какого уровня нужно держать кэши. Нужны ли "КАР", "КАД" и т.п. или их можно восстанавливать из "КА".
 
Когда вы вводите "К", то в ответе сначала возвращаются слова начинающиеся на "КА" (если упорядочивание по алфавиту), потом (если КА не занял всю страницу) начинающиеся на "КБ" и т.д. Возвращайте в этом случае структуры слов на "ка", "кб"... Для последнего, вошедшего на страницу, сочетания так же желательно вернуть общее количество слов в базе. Дальше из этого склеивайте последовательность для "К".
 
Оптимальность зависит во многом от того сколько у вас слов и будет ли пагинатор.

выгружать на клиентский комп 1000000 записей для 1-й буквы?????????

Нет. С постраничным лимитом

тогда выгружая например для той же 1-й "К" с лимитом например 30 мы выгрузим 30 слов, начинающихся на "ка", что не даст абсолютно никаких преимуществ если следующая буква будет скажем "е"

Мы по всякому загружая слова на "К" будем загружать слова на "КА", так почему бы сразу и не запомнить?

ну может тогда имеет смысл их еще и в куках запоминать?. чтоб при обновлении запросы не дублировались.
и где-нить хранить дату последнего обновления таблицы, чтоб при необходимости куки угрохать

излишне

хм.. Киевстара.. знакомый оператор) а ты откуда кстати?

Киев)
 

сколько пользователей одновременно смогут обратится к страничке

Меня не интересует перформанс сервера, меня интересует перформанс клиента, если он на диалапе то качать туда-сюда 1000 записей всетакие не очень приятно. Кстати по поводу сервера там не мускул а оракл, и это не хостер а выделенная площадка.
 

Используйте не примитивные строки, а объекты String(), тогда элементы массивов будут содержать только ссылки на них.

с этого места поподробнее можно?
 

Дальше из этого склеивайте последовательность для "К"

я думаю это излишне, склеивание я пожалуй реализовывать не буду

с этого места поподробнее можно?

В теории:

На практике: внутри каждого конкретного JS-движка возможно использование отложенного копирования для оптимизации первого варианта.
 
Так что в идеале нужно протестировать все браузеры на тему, будет ли где-нибудь выигрыш.