- BEST_PEOPLE (2:5077/15.22) ---------------------- BEST_PEOPLE (RU.UNIX.BSD) -
From : Valentin Nechayev 2:5020/400 19 Jan 01 15:32:48
Subj : hash, dbm и b-tree - какой где применяется и почему
-------------------------------------------------------------------------------
* Forwarded from area 'RU.UNIX.BSD'
From: netch@carrier.kiev.ua (Valentin Nechayev)
DK> А кто такие эти hash, dbm и b-tree. В смысле какой где применяется и
DK> почему.
Есть такая ста-арая;)) юниксовая технология, которая была реализована в виде
dbm, потом ndbm, потом Berkeley DB (она же newdb), потом гнушники сделали
gdbm, а кто-то еще - sdbm и odbm, потом Sleepycat сделал db2 и db3 как
продолжение newdb... Суть такая: есть хранилище данных в виде map'а, он же
хэш, он же ассоциативный массив, и позволяет:
1) записать данные в виде пары ключ - значение,
2) прочитать значение по известному ключу,
3) удалить оные,
4) вывести в произвольном порядке,
5) вывести в отсортированном порядке (это умеет среди перечисленных только
newdb с потомками),
причем ключ и значение заданы как произвольные последовательности байтов.
Sendmail использует от этого всего единственную функцию - указанную выше
под пунктом 2 - а makemap и newaliases строят таблицы для sendmail'а.
Так называемый keyed database в sendmail'е работает поверх чего угодно,
что умеет получить ключ и выдать в ответ значение, если оно есть, или сигнал
отсутствия значения, или код ошибки при попытке получить оное; это может
быть база указанного формата, запуск внешней программы, и т.п.
dbm - это значит базы локального для данного юникса формата hash, доступ к
которым идет через ndbm API. hash - базы newdb (доступ через newdb API)
формата hash. btree - базы newdb формата btree (который позволяет получать
значения в порядке сортировки ключей, что, однако, sendmail не использует).
При сборке бинаря задается дефолтный формат, который будет использоваться,
если не задан формат в описании конкретной сендмыловой keyed database.
Hа солярке, например, это до сих пор dbm. Hа фре - hash. Обычно никто не
меняет формат базы алиасов (хотя можно написать "O AliasFile=dbm /etc/aliases"
и будет работать, но нафига?) и берут hash для остальных. Для баз меньше чем
~2000 ключей hash эффективнее.
Vova
