Здравствуйте, gandjustas, Вы писали:


S>>Здравствуйте, _FRED_, Вы писали:

S>>Создаем индексы Б+ деревья http://rsdn.org/article/alg/tlsd.xml

Автор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.

S>>А по индексам создаем новый файл.
S>>индекс= Строка,смещение. Сортировка по строка.
G>В теории многие так "решили" задачу, а на практике — никто.
В БД это все решено

S>> Ну или можно держать ограниченную длину строки, а при сравнении если сроки одинаковы уже лезть в файл по смещению.
G>Это плохо работает. Проверил, даже код есть.
И на какой длине строки проверял? Стандартный Б+ индекс 8 кб.
Сделай свой в 64 кб. Это если памяти не хватает. А по моему длины даже в 500 байт достаточно.
И это если памяти не хватает. Когда речь идет о 1ГБ это даже не смешно.
Вот когда файлы действительно огромные которые не вмещаются в память, Б+ деревья ооочень эффективны.
Особенно если используются SSD.
Причем можно создавать страницы с переменной длиной строки.
То есть страница загружается в память, выбираются данные в память, а потом двоичным поиском уже идет поиск.
Так или иначе нужно будет обращение к диску если страница незакэширована в памяти.
Обращение же к диску если строки равны и длина их больше чем половина страницы, то будет обращение к диску.
Скорость чтения SSD для 4 кб 500 тыщ в секунду. Вполне себе быстро.

S>>А проще для этого БД какую нибудь использовать
G>С этим тоже успехов что-то не видно.
Да ну? А как же они работают то БД?