B-Tree 인덱스의 구조 및 특징
PostgreSQL의 B-Tree 인덱스는 다중 경로 균형 트리 구조로, 잘 정의된 선형 순서로 정렬될 수 있는 모든 데이터 타입을 인덱싱할 수 있습니다. PostgreSQL B-Tree 인덱스는 각 레벨이 페이지의 이중 연결 리스트로 구성되며, 최하위 레벨의 페이지를 리프 페이지라 하고 다른 모든 레벨은 내부 페이지로 구성됩니다. MySQL InnoDB의 경우 공간 인덱스를 제외한 모든 인덱스가 B-Tree 데이터 구조이며, 인덱스 레코드는 B-Tree의 리프 페이지에 저장됩니다.
실무 운영 시 핵심 메커니즘
리프 페이지에 들어오는 튜플이 맞지 않으면 페이지 분할 작업이 수행되어 넘치는 페이지의 항목을 새 페이지로 이동하며, 상위 페이지에 새 다운링크를 삽입하고 이는 재귀적으로 상위로 연쇄됩니다. InnoDB 인덱스 페이지의 기본 크기는 16KB이며, 페이지 크기는 MySQL 인스턴스 초기화 시 innodb_page_size 설정에 의해 결정됩니다. B-Tree 인덱스는 MVCC 환경에서 동일한 논리 행의 여러 버전이 존재할 수 있음을 직접 인식하지 못하므로, 인덱스된 열이 수정되는 업데이트 작업에서 각 인덱스마다 새로운 튜플 버전이 누적되는 '버전 체른' 현상이 발생합니다.
성능 최적화와 주의사항
B-Tree 인덱스는 등호 및 범위 쿼리를 처리할 수 있으며, 쿼리 플래너는 인덱스된 열이 비교 연산자(<, <=, =, >=, >)에 포함될 때 B-Tree 인덱스 사용을 고려합니다. InnoDB의 innodb_fill_factor 변수는 정렬된 인덱스 빌드 중 각 B-Tree 페이지에 채워지는 공간의 백분율을 정의하며, 나머지 공간은 향후 인덱스 성장을 위해 예약됩니다. 큰 테이블에서는 노드당 키 개수를 높여 트리 깊이를 최소화하는 것이 디스크 I/O 횟수를 크게 줄입니다.