Реализация

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

И сканирование индекса, и вставка кортежей требуют определения местоположения бакета, в котором должен находиться данный кортеж. Для этого нам нужны данные о количестве ведер, highmask и lowmask из metapage; однако по соображениям производительности нежелательно блокировать и фиксировать metapage для каждой такой операции. Вместо этого мы сохраняем кэшированную копию metapage в записи relcache каждого бэкенда. Это позволит получить правильное отображение ведра, если целевое ведро не было разделено с момента последнего обновления кэша.

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

Каждая строка индексируемой таблицы представлена одним кортежем в хэш-индексе. Кортежи хэш-индекса хранятся в страницах bucket и, если они существуют, в страницах overflow. Мы ускоряем поиск, сохраняя записи индекса в одной индексной странице отсортированными по хэш-коду, что позволяет использовать двоичный поиск внутри индексной страницы. Заметим, однако, что нет никаких предположений об относительном упорядочении хэш-кодов на разных индексных страницах ведра.

Алгоритмы разбиения ведер для расширения хэш-индекса слишком сложны, чтобы упоминать их здесь, но более подробно описаны в src/backend/access/hash/README. Алгоритм разбиения является аварийно безопасным и может быть перезапущен в случае неудачного завершения.