Firebird 2.0(ODS 11 이상)용 Firebird 인덱스 구조
Firebird 인덱스 구조 ODS11 이상
새 구조가 도입된 이유는 다음과 같습니다:
- 많은 중복 키 중에서 인덱스 키를 삭제할 때 더 나은 지원 (느린 가비지 컬렉션의 원인)
- 32비트보다 큰 레코드 번호 지원 (40비트)
- 인덱스 키 크기 증가 (페이지 크기의 1/4)
기존 구조 (ODS10 이하):
| header | node | node | node | node | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
header =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // 오른쪽 형제 페이지
SLONG btr\_left\_sibling; // 왼쪽 형제 페이지
SLONG btr\_prefix\_total; // 페이지에 있는 모든 접두사의 합
USHORT btr\_relation; // 일관성을 위한 관계 ID
USHORT btr\_length; // 버킷에 있는 데이터의 길이
UCHAR btr\_id; // 일관성을 위한 인덱스 ID
UCHAR btr\_level; // 인덱스 레벨 (0 = 리프)
struct btn btr\_nodes\[1.;
};
node =
struct btn {
UCHAR btn\_prefix; // 압축된 접두사의 크기
UCHAR btn\_length; // 노드에 있는 데이터의 길이
UCHAR btn\_number\[4.; // 페이지 또는 레코드 번호
UCHAR btn\_data\[1.;
};
end marker = END_BUCKET 또는 END_LEVEL
이들은 리프 노드의 레코드 번호와 비리프 노드의 페이지 번호 대신 사용됩니다.
노드가 END_BUCKET 마커인 경우 다음 형제 페이지의 첫 번째 노드와 동일한 데이터를 포함해야 합니다.
END_LEVEL 마커의 경우 접두사와 길이가 0이므로 데이터가 포함되지 않습니다.
또한 레벨의 모든 첫 번째 노드(리프 페이지 제외)에는 축소된 길이 0 노드가 포함됩니다.
새 ODS11 구조:
| header | jump info | jump nodes | … | node [*] | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
jump info =
struct IndexJumpInfo {
USHORT firstNodeOffset; // 페이지의 첫 번째 노드로의 오프셋 \[\*\]
USHORT jumpAreaSize; // 새 점프 노드가 생성되기 전의 영역 크기
UCHAR jumpers; // 페이지의 점프 노드 수, 최대 255
};
jump node =
struct IndexJumpNode {
UCHAR\* nodePointer; // 페이지에서 이 노드를 읽을 수 있는 포인터
USHORT prefix; // 이전 점프 노드에 대한 접두사 길이
USHORT length; // 점프 노드의 데이터 길이 (접두사와 함께 이 값은
가리키는 노드의 접두사가 됨)
USHORT offset; // 페이지에서 노드까지의 오프셋
UCHAR\* data; // 여기서 데이터를 읽을 수 있음
};
새 인덱스 구조를 위한 새 플래그:
header->pag_flags에 새 플래그가 추가됩니다.
btr_large_keys (32) 플래그는 압축된 길이/접두사와 레코드 번호를 저장하기 위한 것입니다. 이는 길이와 접두사가 페이지 크기의 1/4(4096 페이지 크기의 경우 1024)까지 가능하며, 향후 디스크 구조를 다시 변경하지 않고도 쉽게 확장할 수 있습니다. 또한 레코드 번호도 예를 들어 40비트로 쉽게 확장할 수 있습니다. 이러한 숫자는 7비트 단위로 저장되며 최상위 1비트가 마커로 사용됩니다(가변 길이 인코딩). 저장해야 하는 새 바이트마다 7씩 이동합니다. 예: 25는 1바이트 0x19로 저장되고, 130은 2바이트 0x82 0x01로, 65535는 3바이트 0xFF 0xFF 0x03으로 저장됩니다.
중복 노드:
또한 모든 노드(비리프 페이지)에 레코드 번호를 저장하기 위한 새 플래그가 추가되었습니다. 이는 많은 중복이 있는 경우 인덱스 검색 속도를 높입니다. 이 플래그는 btr_all_recordnumber (16)입니다. 이 추가 정보를 통해 중복이 많은 삽입/삭제 시 키 조회(외래 키의 NULL 등)가 훨씬 빨라집니다(가비지 컬렉션도 포함!). 또한 중복 노드(길이 = 0)는 길이 정보를 저장하지 않으며, 첫 번째 저장 바이트의 3비트를 사용하여 이 노드가 중복인지 판단합니다. ZERO_LENGTH (4) 외에도 END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) 및 ONE_LENGTH (5) 마커가 있습니다. 숫자 6과 7은 향후 사용을 위해 예약되어 있습니다.
점프 노드:
점프 노드는 페이지 어딘가에 있는 노드에 대한 참조입니다.
특정 노드에 대한 오프셋 정보와 참조된 노드의 접두사 데이터를 포함하지만, 점프 노드 자체에도 접두사 압축이 적용됩니다.
이상적으로는 jumpAreaSize마다 발견되는 첫 번째 노드 다음에 새 점프 노드가 생성되지만, 이는 인덱스를 비활성화/활성화하거나 인덱스에 저장될 순서와 동일한 순서로 노드를 삽입하는 경우에만 해당됩니다.
두 점프 노드 참조 사이에 노드가 삽입되면 오프셋만 업데이트되며, 오프셋이 특정 임계값(+/-10%)을 초과하지 않는 경우에만 해당됩니다.
노드가 삭제되면 오프셋만 업데이트되거나 점프 노드가 제거됩니다. 이는 마지막 점프 노드와 첫 번째 노드 사이에 약간의 공백이 존재할 수 있음을 의미하며, 새 점프 노드를 생성하는 데 시간을 낭비하지 않습니다.
접두사와 길이도 가변 길이 인코딩으로 저장됩니다.
예제 데이터:
(x) = x바이트 크기
| header (34) | ||||
| 52 (2) | 256 (2) | 2 (1) | 30 (2) | 0 (1) |
| 2 (1) | 260 (2) | FI (2) | 1 (1) | 1 (1) |
| 514 (2) | U (1) | 0 (1) | 1 (1) | 0 (1) |
| A (1) | … | |||
| 2 (1) | 6 (1) | 21386 (3) | REBIRD (6) | … |
| 2 (1) | 2 (1) | 1294 (2) | EL (2) | … |
고정 헤더 이후 포인터 = 0x22
점프 정보 이후 포인터 = 0x29
첫 번째 점프 노드로의 포인터 = 0x29 + 6 (점프 노드 1) + 5 (점프 노드 2) = 0x34
점프 노드 1은 FIREBIRD를 데이터로 나타내는 노드를 참조합니다. 이 노드의 접두사가 2이므로 처음 2문자 FI도 점프 노드에 저장됩니다.
다음 점프 노드는 접두사가 2인 FUEL을 나타내는 노드를 가리킵니다. 따라서 점프 노드 2에는 FU가 포함되어야 하지만, 이전 노드에 이미 F가 포함되어 있으므로 접두사 압축으로 인해 이 문자는 무시되고 U만 저장됩니다.
NULL 상태:
저장해야 할 데이터는 btr.cpp의 compress() 프로시저에서 결정됩니다.
ASC(오름차순) 인덱스의 경우 데이터가 저장되지 않습니다(키 길이가 0). 이렇게 하면 자동으로 인덱스의 첫 번째 항목이 되어 올바른 순서가 유지됩니다(단일 필드 인덱스의 경우 노드 길이와 접두사가 0).
DESC(내림차순) 인덱스는 값이 0xFF(255)인 단일 바이트를 저장합니다. 값(빈 문자열은 255가 될 수 있음)과 NULL 상태를 구분하기 위해 데이터 앞에 0xFE(254) 바이트를 삽입합니다. 이는 0xFF(255) 또는 0xFE(254)로 시작하는 값에만 적용되므로 올바른 순서가 유지됩니다.
예제:
| ASC 인덱스 노드, 1세그먼트 | |||
| prefix | length | 저장된 데이터 | 실제 값/상태 |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| DESC 인덱스 노드, 1세그먼트 | |||
| prefix | length | 저장된 데이터 | 실제 값/상태 |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| ASC 인덱스 노드, 3세그먼트 | |||
| prefix | length | 저장된 데이터 | 실제 값/상태 |
| 0 | 0 | NULL,NULL, NULL | |
| 0 | 10 | x01(1) x70(F) x73(I) x82(R) x69(E) x01(1) x66(B) x73(I) x82(R) x68(D) | NULL, NULL, FIREBIRD |
| 0 | 10 | x02(2) x70(F) x73(I) x82(R) x69(E) x02(2) x66(B) x73(I) x82(R) x68(D) | NULL, FIREBIRD, NULL |
| 0 | 10 | x03(3) x70(F) x73(I) x82(R) x69(E) x03(3) x66(B) x73(I) x82(R) x68(D) | FIREBIRD, NULL, NULL |
| 3 | 9 | x00(0) x00(0) x02(2) x65(A) x00(0) x00(0) x00(0) x01(1) x66(B) | FI, A, B |
| … | … | … | … |
| DESC 인덱스 노드, 3세그먼트 | |||
| prefix | length | 저장된 데이터 | 실제 값/상태 |
| 0 | 12 | xFC xB9 xB6 xFF xFF xFD xBE xFF xFF xFF xFE xBD | FI, A, B |
| 3 | 17 | xAD xBA xFC xBD xB6 xAD xBB xFD xFF xFF xFF xFF xFE xFF xFF xFF xFF | FIREBIRD, NULL, NULL |
| 1 | 19 | xFF xFF xFF xFF xFD xB9 xB6 xAD xBA xFD xBD xB6 xAD xBB xFE xFF xFF xFF xFF | NULL, FIREBIRD, NULL | | 6 | 14 | xFF xFF xFF xFF xFE xB9 xB6 xAD xBA xFE xBD xB6 xAD xBB | NULL, NULL, FIREBIRD | | 11 | 4 | xFF xFF xFF xFF | NULL,NULL, NULL | | | | | END_LEVEL |
c ABVisie 2005, Arno Brinkman