페이지 헤더

• 탐색과 유지보수, 최적화에 필요한 페이지에 대한 정보를 저장한다.
  • PostgreSQL : 페이지크기, 레이아웃 버전
  • MySQL InnoDB : 힙 레코드 개수와 레벨, 기타 구조 관련값
  • SQLite : 셀 개수와 가장 오른쪽 포인터

매직넘버

• 상수 값을 포함하는 멀티바이트 블록이다.
• 페이지의 버전, 종류같은 정보를 포함한다.
• 검증과 상태 체크에도 사용된다.
  • 임의의 오프셋의 바이트 열이 매직 넘버와 정확히 일치할 가능성이 매우 낮기 때문에, 일치한다면 높은확률로 유효하다고 볼 수 있으니까!

하이 키

• 가장 오른쪽 포인터는 다음 리프 노드를 가리키는 포인터이고,
• 이때, 가장 오른쪽 포인터와 함께 하이키를 저장하는데, 하이키는 해당 리프 노드에 저장된 키 값 중 가장 큰 값으로, 다음 리프 노드의 첫 번째 키와 같거나 큰 값이다.
• 이런 형식의 트리를 b-link-tree 라고 부르고 PostgreSQL에서 사용한다.
  • B-link-tree가 그래서 뭔데…
    • B-Link 트리는 B-트리의 변형이다.
    • 링크를 사용하여 데이터를 연결하고 검색하는 데 특화되어 있다.
    • 특징 (참고)

Q. 하이키 방식에선 가장 오른쪽에 키를 추가함. 만약 가장 오른쪽의 리프 노드의 하이키는 어떤 키가 와야 할까요?

• A

오버플로우 페이지

• 노드의 크기와 트리 팬아웃은 고정 값이며 동적으로 변하지 않는다.
• 근데, 값에 따라서 값이 너무 크면 페이지를 넘어갈 수도 있고 너무 작으면 페이지를 낭비할 수도 있는 상황이 발생한다.
• 따라서, 페이지 크기 증가 및 확장은 불가피하다.
• 만약에 4K인 페이지로 설정했는데, 5K의 값을 저장하고 싶다면
  • 페이지를 5K로 늘리는게 아니라, 4K + 4K 페이지를 가지고 넘는 페이지를 원본페이지에 연결한다.
  • 이때, 넘어가는 페이지를 오버플로우 페이지라, 원본페이지를 프라이머리 페이지 라고한다.
• 고정크기는 노드 크기를 팬아웃으로 나눈 값이다.
• 오버플로우 페이지는 특별관리가 필요하다.
  • 기본페이지처럼 페이지 단편화가 발생할 수 있다.