해시 인덱스에는 네 가지 종류의 페이지가 있습니다: 정적으로 할당된 제어 정보를 포함하는 메타 페이지(페이지 0); 기본 버킷 페이지 오버플로 페이지; 해제되어 재사용 가능한 오버플로 페이지를 추적하는 비트맵 페이지도 있습니다. 주소 지정을 위해 비트맵 페이지는 오버플로 페이지의 하위 집합으로 간주됩니다.

색인 스캔과 튜플 삽입 모두 주어진 튜플이 위치해야 하는 버킷을 찾아야 합니다. 이를 위해서는 메타페이지의 버킷 수, 하이마스크, 로우마스크가 필요합니다. 그러나 이러한 모든 작업에 대해 메타페이지를 잠그고 고정해야 하는 것은 성능상의 이유로 바람직하지 않습니다. 대신 각 백엔드의 relcache 항목에 메타페이지의 캐시된 복사본을 유지합니다. 마지막 캐시 새로 고침 이후 대상 버킷이 분할되지 않은 한 올바른 버킷 매핑이 생성됩니다.

기본 버킷 페이지와 오버플로 페이지는 특정 인덱스에 버킷 수에 비해 더 많거나 적은 오버플로 페이지가 필요할 수 있으므로 독립적으로 할당됩니다. 해시 코드는 흥미로운 주소 지정 규칙 세트를 사용하여 기본 버킷 페이지가 생성된 후 이동할 필요 없이 다양한 수의 오버플로 페이지를 지원합니다.

인덱싱된 테이블의 각 행은 해시 인덱스의 단일 인덱스 튜플로 표시됩니다. 해시 인덱스 튜플은 버킷 페이지에 저장되며, 존재하는 경우 오버플로 페이지에 저장됩니다. 우리는 해시 코드로 정렬된 하나의 색인 페이지에 색인 항목을 유지하여 색인 페이지 내에서 이진 검색을 사용할 수 있도록 하여 검색 속도를 높입니다. 그러나 버킷의 여러 인덱스 페이지에 걸쳐 해시 코드의 상대적 순서에 대한 가정은 *아닙니다*.

해시 인덱스를 확장하기 위한 버킷 분할 알고리즘은 너무 복잡하여 여기서 언급할 가치가 없습니다. 하지만 더 자세히 설명되어 있습니다.src/백엔드/액세스/해시/README. 분할 알고리즘은 충돌로부터 안전하며 성공적으로 완료되지 않으면 다시 시작할 수 있습니다.