B-Tree 인덱스
B-Tree 인덱스
PostgreSQL에서 가장 기본적이면서도 가장 많이 쓰이는 인덱스가 바로 B-Tree 인덱스예요. 정렬 순서가 명확하게 정의된 데이터라면 어떤 타입이든 B-Tree로 인덱스를 만들 수 있어요. 그래서 정렬 의미론을 표현하는 시스템 전반의 기준으로도 자리를 잡고 있죠.
본문
인덱스로 만들 수 있는 조건
B-Tree는 다중 방향 균형 트리(multi-way balanced tree) 구조예요. 어떤 데이터 타입이든 잘 정의된 선형 순서로 정렬할 수 있다면 B-Tree 인덱스를 만들 수 있답니다. 다만 인덱스 항목 하나가 대략 페이지의 3분의 1을 넘지 않아야 한다는 제약이 있어요(TOAST 압축을 거친 경우도 마찬가지예요).
여기서 재미있는 점은 B-Tree 인덱스 자체보다 그 의미론이 더 널리 쓰인다는 거예요. 각 B-Tree 연산자 클래스가 자기 데이터 타입에 정렬 순서를 부여하기 때문에, 이 연산자 클래스(혹은 연산자 패밀리)가 PostgreSQL 전반의 정렬 의미를 표현하는 기준이 됐어요. 그래서 B-Tree 인덱스를 지원하는 데 필요한 것보다 더 많은 기능을 갖고 있고, B-Tree와는 꽤 먼 곳에 있는 시스템 부분도 이걸 사용하죠.
B-Tree 연산자 클래스의 동작
B-Tree 연산자 클래스는 다섯 가지 비교 연산자, 즉 <, <=, =, >=, >를 제공해야 해요. <>도 연산자 클래스에 넣어야 할 것 같지만 실제로는 그렇지 않아요. <> 조건을 인덱스 검색에 쓰는 건 거의 유용하지 않기 때문이에요. (일부 목적에서는 플래너가 <>를 B-Tree 연산자 클래스와 연관 지어 다루기는 하는데, 그건 = 연산자의 부정 링크를 통해서 찾아낸답니다.)
여러 데이터 타입이 거의 동일한 정렬 의미를 공유하면, 그 연산자 클래스들을 하나의 연산자 패밀리로 묶을 수 있어요. 이렇게 하면 플래너가 타입 간 비교에 대한 추론을 할 수 있어서 유리해요. 패밀리 안의 각 연산자 클래스는 자기 입력 타입에 대한 단일 타입 연산자(와 관련 지원 함수)를 담고, 타입 간 비교 연산자와 지원 함수는 패밀리 안에서 "느슨하게" 둬요. 이행성(transitivity)에서 추론하는 모든 비교 조건을 플래너가 표현할 수 있도록, 타입 간 연산자의 완전한 집합을 패밀리에 포함하는 것이 권장돼요.
반드시 만족해야 하는 기본 가정
B-Tree 연산자 패밀리가 제대로 동작하려면 몇 가지 기본 가정을 만족해야 해요. = 연산자는 동치 관계(equivalence relation)여야 해요. 즉 타입의 모든 null 아닌 값 A, B, C에 대해 다음이 성립해야 하죠.
A = A는 참이에요 (반사 법칙)A = B이면B = A예요 (대칭 법칙)A = B이고B = C이면A = C예요 (이행 법칙)
< 연산자는 강한 순서 관계(strong ordering relation)여야 해요.
A < A는 거짓이에요 (비반사 법칙)A < B이고B < C이면A < C예요 (이행 법칙)
그리고 그 순서는 전체적(total)이어야 해요. 모든 null 아닌 값 A, B에 대해 A < B, A = B, B < A 중 정확히 하나만 참이어야 하죠. 이것이 삼분 법칙(trichotomy law)인데, 비교 지원 함수의 정의를 정당화해 주는 근거예요. 나머지 연산자들은 =와 <로부터 자연스럽게 정의되고, 그들과 일관되게 동작해야 해요.