АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ГЛАВА II ПРОЕКТНЫЙ РАЗДЕЛ

Читайте также:
  1. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  2. А. Все разделы внутренних болезней.
  3. А. Общая морфология и подразделение на дольки
  4. А. Подразделение на 3 доли
  5. Аллах извлек потомство Адама из его спины после сотворения его и разделил их на обитателей Рая и Ада
  6. В) Международного разделения труда и специализации производства и интеграции хозяйственных процессов
  7. В) Совокупность взаимосвязанных и взаимодействующих друг с другом национальных рынков отдельных государств, участвующих в международном разделении труда
  8. Вопрос 229. На какое количество групп разделяют действия, составляющие инцидент?
  9. Вторая глава
  10. Второй раздел моего дипломного проекта – Электротехническая часть.
  11. Высшее должностное лицо (глава) субъекта Федерации: правовое положение и полномочия
  12. Глава 1

 

Принцип построения хеш – функций

Многочисленные тесты показали хорошую работу двух основных типов хеширования, один из которых основан на делении, а другой на умножении. Впрочем, это не единственные методы, которые существуют, более того, они не всегда являются оптимальными.

По мере роста базы данных можно

· пользоваться изначальной хеш-функцией, теряя производительность из-за роста коллизий;

· выбрать хеш-функцию «с запасом», что повлечет неоправданные потери дискового пространства;

· периодически менять функцию, пересчитывать все адреса. Это отнимает очень много ресурсов и выводит из строя базу на некоторое время.

Существует техника, позволяющая динамически менять размер хеш-структуры. Это – динамическое хеширование. Хеш-функция генерирует так называемый псевдоключ (“pseudokey”), который используется лишь частично для доступа к элементу. Другими словами, генерируется достаточно длинная битовая последовательность, которая должна быть достаточна для адресации всех потенциально возможных элементов. В то время, как при статическом хешировании потребовалась бы очень большая таблица (которая обычно хранится в оперативной памяти для ускорения доступа), здесь размер занятой памяти прямо пропорционален количеству элементов в базе данных. Каждая запись в таблице хранится не отдельно, а в каком-то блоке (“bucket”). Эти блоки совпадают с физическими блоками на устройстве хранения данных. Если в блоке нет больше места, чтобы вместить запись, то блок делится на два, а на его место ставится указатель на два новых блока.

Задача состоит в том, чтобы построить бинарное дерево, на концах ветвей которого были бы указатели на блоки, а навигация осуществлялась бы на основе псевдоключа. Узлы дерева могут быть двух видов: узлы, которые показывают на другие узлы или узлы, которые показывают на блоки. Например, пусть узел имеет такой вид, если он показывает на блок:

 

Zero Null
Bucket Указатель
One Null

 

Если же он будет показывать на два других узла, то он будет иметь такой вид:

 

Zero Адрес a
Bucket Null
One Адрес b

 

Вначале имеется только указатель на динамически выделенный пустой блок. При добавлении элемента вычисляется псевдоключ, и его биты поочередно используются для определения местоположения блока. Например, элементы с псевдоключами 00… будут помещены в блок A, а 01… - в блок B. Когда А будет переполнен, он будет разбит таким образом, что элементы 000… и 001… будут размещены в разных блоках.

 


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)