Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > MySQL > что такое хэш-таблицы и В-деревья?


Автор: ida 26.4.2004, 10:25
В переводе документации на MySQL есть такие вещи:

Цитата
Очень быстрая система распределения памяти, базирующаяся на потоках.
Очень быстрые соединения, использующие оптимизированный метод однопроходного мультисоединения (one-sweep multi-join).
Очень быстрые дисковые таблицы на основе В-деревьев со сжатием индексов.
Хеш-таблицы в памяти, используемые как временные таблицы.


Вопрос - что такое хэш-таблицы? что здесь подразумевается под дисковыми таблицами? что такое В-деревья? что означает "сжатие индексов"? что такое однопроходные мультисоединения?

Автор: HalkaR 26.4.2004, 19:21
B-деревья - это двоичные деревья, т.е. деревья, где у каждого узла два потомка. Хэш таблицы, знаю, но обьяснить не смогу notify.gif

Автор: ida 26.4.2004, 21:16
Мдя... как бы еще понять что все это значит применительно к БД и на фиг оно все там нужно... smile.gif

Автор: sergejzr 26.4.2004, 22:22
Зачем БД деревья?
В БД необходима структура которая:
  • позволяет хранить отсортированные данные.
  • позволяет добавлять новые данные. При этом сортировка не имеет права нарушаться.
  • позволяет частичную выгрузку данных в память. При этом сортировка тоже не имеет права нарушаться.
  • итд..
В БД данные хранятся парами [даты/дата ключ].
Пример таблица
имя,фамилия,рост,вес,цвет глаз,дата рождения:
вася|иванов|170|80|зелёный|12.01.1975|
петя|синицын|165|60|чёрный|12.01.1974|

допустим ключ это имя. Тогда ведь совсем необязательно при работе с БД грузить в оперативку все данные. Достаточно загрузить только имена. Ключ содержит дополнительно позицию данных в файле.
Для быстрого поиска конкретного ключа, собирается дерево. В нём ключи частично просортированы. Как конкретно, тут уже надо тебе читать/разбираться.
-----------------------------------------------------------------------------------------------------------------------------------------------
Грубо про хэш (он тоже для быстрого поиска):

Xэш -функция:
индех(стринг) (как f(x));
существует массив ([0..N]), существуют данные (стринги) в хаш-функцию передаём стринг, она высчитывет некое число у 0<=у<=N. Это и есть индекс в массиве. На этот индекс в массив записываются данные.

Теперь, если ищем этот стринг в массиве, то по той же функции высчитываем индех и читаем данные(это естессно офигительно быстро). Конечно существует вероятность того, что функция даст один ответ на два разных стринга. Поэтому каждый елемент массива-лист. То есть находим индекс , а дальше ищем по листу.
------------------------------------------------------------------------------------------------------------------------------------------------


Надеюсь обьяснил более-менее понятно в двух словах. Но! Теория идёт значительно глубже! Так что читай обязательно подробные материалы.

Добавлено @ 22:26
Немного странно что в теме указано "применительно к MySQL". Эти вещи для любой БД.

Автор: Cashey 27.4.2004, 11:44
Цитата(sergej @ 26.4.2004, 22:22)
Грубо про хэш (он тоже для быстрого поиска):

Xэш -функция:
индех(стринг) (как f(x));
существует массив ([0..N]), существуют данные (стринги) в хаш-функцию передаём стринг, она высчитывет некое число у 0<=у<=N. Это и есть индекс в массиве. На этот индекс в массив записываются данные.


Странно, помоему хэш-функции это основа алгоритма криптографирования данных, основанных на открытом и закрытых ключах

Автор: sergejzr 27.4.2004, 11:49
А чего мешает её применять (немного модифицировав) в обоих случаях?
В криптографии она так же выдаёт число. Число это идентифицирует мессагу.

Автор: sergejzr 7.5.2004, 16:05
ida
Тут подробнее по тематике. Так же конкретный линьк по индексации в Мускуле.
http://forum.vingrad.ru/index.php?showtopic=22020

PS: Неплохо было бы услышать, пригодилась информация или нет..... bored.gif

Автор: ida 7.5.2004, 20:28
Медленно пригождается вместе со всей документацией, читаемой перед защитой диплома smile.gif Спасибо. Просто не люблю плавать в терминологии на экзаменах.

Автор: stron 7.5.2004, 22:13
Вспоминается кое-что из ТИЛСа (Теории инф. логич. систем)

B-деревья (пример):
...........................
[*10*20*] - узел
/ | \
5 15 25 - лист

В В-деревьях очень быстро происходит поиск сложность алгоритма, если не напутал, log2(n)

Применительно к БД:
замени числа (5,15,25...) на значения индекса, и получишь ускорение SELECT'ов по индексируемому полю

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)