70.2. Реализация#
70.2. Реализация
В хеш-индексе есть четыре типа страниц: мета-страница (страница ноль), которая содержит статически выделенную управляющую информацию; основные страницы корзин; страницы переполнения; и страницы битовой карты, которые отслеживают освобожденные страницы переполнения, доступные для повторного использования. В целях адресации, страницы битовой карты рассматриваются как подмножество страниц переполнения.
Сканирование индекса и вставка кортежей требуют определения ведра, в котором должен находиться заданный кортеж. Для этого нам нужно знать количество ведер, highmask и lowmask из метапейджа. Однако, из-за проблем с производительностью нежелательно блокировать и закреплять метапейдж для каждой такой операции. Вместо этого мы сохраняем кешированную копию метапейджа в каждой записи relcache каждого бэкенда. Это обеспечит правильное отображение ведер, пока целевое ведро не было разделено с момента последнего обновления кеша.
Первичные страницы корзин и переполнения выделяются независимо, так как любому индексу может потребоваться больше или меньше страниц переполнения по сравнению с соответсвующим количеством корзин. Хеш-код использует интересный набор правил адресации для поддержки переменного количества страниц переполнения, не требуя перемещения первичных страниц корзин после их создания.
Каждая строка в индексированной таблице представлена одним индексным кортежем в хеш-индексе. Индексные кортежи хеш-индекса хранятся на страницах корзины и, если они существуют, на страницах переполнения. Мы ускоряем поиск, сохраняя записи индекса на любой странице индекса, отсортированными по хеш-коду, что позволяет использовать двоичный поиск внутри страницы индекса. Однако следует отметить, что существует вариант «нет» об относительном порядке хеш-кодов на разных страницах индекса корзины.
Алгоритмы разделения корзин для расширения хеш-индекса слишком сложны, чтобы упоминать их здесь, но они подробно описаны в файле src/backend/access/hash/README.
Алгоритм разделения является надежным и может быть перезапущен, если не завершен успешно.