Javascript база данных

Есть такой анекдот (или притча) о злой тётке, которая один раз в жизни пожалела нищенку и подала луковое пёрышко; а потом в аду черти тётку топили, а нищенка протянула ей то самое луковое пёрышко и вытянула за него из воды.

Мы, правоверные (католики и православные), не верим в предопределение, но по мериканским меркам (каждому ведь будет по его вере?) можно считать доказанным научным фактом то, что корпорация Микрософт после смерти попадёт в ад и черти будут её топить в том дерьме, которым она наводнила мир.

Но есть как минимум два луковых пёрышка для MS (которые лично я бы ей протянул): формат chm и объект браузера tabular data control. В сочетании друг с другом они позволяют создавать локальные базы данных – такие, как, например, Орфографический словарь Лопатина размером в 160000 строк с возможностью поиска слов и использования его в качестве обратного словаря.

Чтобы добиться хотя бы слабого подобия такой мощности в других браузерах, приходится сильно напрягать мозг. Всё равно скорость работы с текстовой (или HTML) базой данных получается на порядок ниже – отчасти потому что нет специального объекта (и БД приходится эмулировать), отчасти потому что в формате chm скорость заметно повышается из-за компиляции. Можно, конечно, сделать скрипт специально для Гугл Хром и попытаться его ускорить, запихав HTML-страницы в chm, но попавшие в chm страницы открываются только с помощью ИЕ...

Три источника ускорения Javascript базы данных

Это история многолетнего (ну, год и два месяца) напряжённого поиска эффективных алгоритмов сортировки и отбора данных в HTML-таблицах. История, которая укладывается в три пункта.

1. Как выводить отсортированные данные на экран?

   Тут изначально были две конкурирующие технологии: по одной строке (appendChild) или собрать все элементы отсортированного массива в строку и затем обновить innerHTML таблицы. Оказалось, оба способа плохи. На самом деле, конечно, для сильных браузеров (Сафари, Хром) оба способа пофиг (скорости всегда запредельные). А плохи – для ИЕ: innerHTML даёт некоторый выигрыш в скорости на средних объёмах, но при увеличении таблицы до некоторой «критической массы», тормоз становится фатальным (работа, в принципе, делается, но по 20 секунд пользователь ждать сортировки не будет). А при appendChild время сортировки в ИЕ просто растёт пропорционально количеству строк таблицы (а с учётом того, что оно и так больше, чем у конкурентов, получаются те же яйца, только в профиль).

   Решение я нашёл на странице TinyTable. Точнее, это автор TinyTable (Michael Leigeber) нашёл решение (или тоже у кого-то позаимствовал? – никому нельзя верить...), а я им воспользовался. Это, если можно так сказать, эмуляция innerHTML с помощью replaceChild: отсортированная таблица формируется всё-таки с помощью appendChild, но формируется не сразу на своём месте в DOM, а в виртуальном пространстве, «в тени».

   Делается это так: создаётся node tbody (createElement("tbody")), но никуда с помощью appendChild не присоединяется! И вот к этому, висящему в «подпространстве» DOM элементу, с помощью appendChild добавляются отсортированные строки таблицы. И просходит это просто с бешеной скоростью (в любом браузере). А потом, с помощью replaceChild, старый tbody меняется на новый (сгенерированный скриптом) – что вполне можно считать аналогом использования innerHTML.

2. Обязательно должна быть разбивка на страницы.

   Будь движок сортировки самым раскрутым (хоть на основе того же TDC в ИЕ), будь метод обновление DOM самым идеальным – в любом браузере всегда останется такая гиря, как вывод на экран. Это всё-таки разные действия для браузера: загрузить страницу и вывести на экран страницу.

   Попробуйте просто открыть HTML-страницу (без всяких скриптов) с таблицей размером, скажем, в 1 МБ (например, latrus-full.htm) – сколько времени ждать придётся? И попробуйте загрузить ту же страницу с правилом table {display:none;} (пример: latrus-null.htm). Есть разница?

   Методика работы с TDC обязательно предусматривает постраничный вывод (иначе работа с большими таблицами была бы в принципе невозможна). Почему бы не позаимствовать эту полезную черту для Javascript базы данных?

3. Не надо сортировать всю таблицу.

   Природу не обманешь, и самый лучший алгоритм сорторовки массива на Javascript без компиляции будет работать медленно. То есть, например, Латинско-русский словарь в 14000 строк на Pentium 4 (2.5 GHz) сортируется с учётом создания массива 2 секунды (что, наверное, всё-таки нельзя считать рабочим режимом).

   Но какой дурак захочет сортировать Латинско-русский словарь (который и так отсортирован по алфавиту)? Да и не только словарь, а вообще – зачем сортировать огромные таблицы? При наличии огромного огорода данных первичной потребностью пользователя всегда будет отбор.

   Тут-то и возникает третий принцип (или приём): сортировать только отфильтрованные данные. То есть сначала пользователь выбирает из 5000 строк хотя бы 500 (а в норме – 50), а потом, при необходимости, сортирует. А если пользователь выбирает данные по нескольким столбцам, отбор производится по принципу «искать в найденном», и количество строк будет уменьшаться прямо катастрофически.

   Пользователи, конечно, глупые, и всегда будут делать всё наоборот. Но тут у них будет хороший стимул делать всё правильно – самообучающая система. Хотя и напоминание от программиста типа «Фильтруй данные перед сортировкой!» (с отказом программы выполнять сортировку больше определённого объёма) тоже не помешает.

Выводы

1. Таблицу в 14000 строк несложно загрузить в браузер, если выводить на экран небольшими частями (постранично).
2. При отборе (фильтрации) данных нужно создавать новый массив, состоящий только из найденных данных, и дальнейшие манипуляции (отбор, сортировка) производить уже с этим массивом (а не с массивом всех строк).
3. Часть данных, с которыми при сортировке и фильтрации имеет дело Javascript, является ссылками на элементы DOM (в нашем случае – строки таблицы). Сами элементы (на которые указывают ссылки) не должны быть привязаны к конкретному месту в DOM (с помощью appendChild); а если они были в DOM изначально (в HTML-коде), их надо переместить оттуда в «ничейное» пространство.

Дистрибутив и примеры работы

Все необходимые для работы скрипта файлы есть в архиве BigTableSorter.zip. Из файла примера (limit202.htm), находящегося там же, понятно, как подключать скрипт и CSS к HTML-странице (так же, как предыдущую версию test-tracker/tabsort2.1.js).

Пример работы: Латинско-русский словарь (~14000 слов).