LINUX.ORG.RU

хеш-таблица на диске

 , ,


3

2

посоветуйте алгоритмы или готовые реализации хеш-таблицы, которая хранится на диске?

ключ: битовая строка (желательно, но не обязательно, произвольной длины)

данные: фиксированное количество бит

критерии: минимальный объем на диске, быстрое время доступа на чтение, не слишком требовательно к озу (т.к. для десктопа).

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

сам хеши почти никогда не реализовывал, только пользовался, и немного знаю в теории.

★★★★★

Последнее исправление: MyTrooName (всего исправлений: 1)
Ответ на: я ничего не понял от Stil

Почему не БД по вкусу?

в основном потому, что индекс в базе - единственный, и это хеш.

sql - однозначно переусложнение, nosql рассматриваю. тонкость в том, что размер ключа сильно варьируется (его можно круто сжать хафменом), и хотелось бы этим воспользоваться, чтобы сократить объем бд.

MyTrooName ★★★★★
() автор топика
Ответ на: комментарий от MyTrooName

Про BDB ещё добаволю, что желательна версия 1.85. (В более поздних поменяли лицензию. Кое-какие фишки добавили, но они и не очень нужны.)

Начинать от сюда: http://mdoc.su/o/dbopen

beastie ★★★★★
()
Последнее исправление: beastie (всего исправлений: 2)

самое главное забыл указать: база генерится один раз, дальше идет только доступ на чтение, соответственно, хотелось бы её сделать максимально плотной.

MyTrooName ★★★★★
() автор топика
Ответ на: комментарий от MyTrooName

Если ключи префиксообразные, то профит даст btree(3) — он хранит префикс на страницу, а в ключах только суффикс. Будешь сжимать, учитывай.

arturpub ★★
()
Ответ на: комментарий от MyTrooName

самое главное забыл указать: база генерится один раз, дальше идет только доступ на чтение, соответственно, хотелось бы её сделать максимально плотной.

Ну дак выкати дамп базы.

Carb_blog4
()
Ответ на: комментарий от MyTrooName

Без разницы. Полный дамп ключей, если нужен только индекс.

Carb_blog4
()
Ответ на: комментарий от aedeph_

Плюсану perfect hash. ТСу: Еще почитай в седжвике про extendible hashing. Только мне кажется это малость бесполезная структура данных (ext. hash), если поиск по ключу равновероятный для всех элементов, потому что будет скорость доступа = скорости сика диска, т.е. не более сотни в секунду.

nerdogeek
()
Последнее исправление: nerdogeek (всего исправлений: 1)

Ещё tdb (trivial database) - это именно хеш. Из плюсов - возможность одновременной записи разных ключей из разных процессов. Из минусов - невозможность одновременного использования из разных потоков одного процесса. tdb используется много где, - например, в samba.

Sorcerer ★★★★★
()
Ответ на: комментарий от stevejobs

Как нельзя, а 1.86?

Для справки, алгоритм условно тривиален, и в современной bdb присутствует практически в неизменном виде. Каждая мажорная версия добавляла образно по одной букве из acid и еще кое-какие фишки, но не меняла storage.

arturpub ★★
()
Ответ на: комментарий от MyTrooName

Придумать как лучше gperf запустить? Например из консоли.

Ключей-то много? А то тут по всем исходным данным gperf в полный рост.

anonymous
()
Ответ на: комментарий от arturpub

бисти же написал, что в более поздних поменяли лицензию, поэтому последняя нужная - 85. Неправильно понял его?

stevejobs ★★★★☆
()
Ответ на: комментарий от MyTrooName

BDB есть просто везде. Библиотека очень маленькая, но при этом «не в бровь, а в глаз». Её можно даже статически залинковать. Но всё таки сильно советую не актуальную версию, а 1.85 или 1.86.

ref: http://www.oracle.com/technetwork/products/berkeleydb/downloads/index-082944....

beastie ★★★★★
()
Ответ на: комментарий от MyTrooName

ключей много. столько, сколько на диск влезет

Тогда BDB использовать рискованно. Лучше скорее всего придумать свой велосипед...

хотелось бы больше - да нельзя

...с компрессией и дедупликацией

anonymous
()
Ответ на: комментарий от anonymous

с компрессией

компрессию делаю на ключах. идей по компрессии самого хеша нет (может, посоветуете чего на будущее)

дедупликацией

это ж хеш, чего там дедуплицировать-то еще?

MyTrooName ★★★★★
() автор топика
Ответ на: комментарий от beastie

у тебя, случайно, не завалялось порта 1.85 под win32 или mingw?

нашел неофициальный, но пока не удается завести

MyTrooName ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.