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