B-Tree 인덱스 구조와 탐색: Root·Branch·Leaf·ROWID

핵심 요약

Oracle 공식 문서는 일반적인 인덱스 구조를 B-tree index라고 부릅니다. 국내 SQL 튜닝 교재에서는 같은 계열의 구조를 관례적으로 B*Tree라고 표현하기도 합니다. 이 이론에서는 Oracle 공식 용어인 B-tree를 기본으로 사용하되, B*Tree 표기가 같은 학습 맥락에서 사용될 수 있음을 전제로 합니다.

Root·Branch Block
  → Key 범위와 Child Block Pointer로 시작 Leaf 탐색

Leaf Block
  → 정렬된 Index Entry 저장
  → Heap Table이면 Key와 ROWID로 실제 Row 위치 연결
  → Leaf Block끼리 양방향 연결

범위 조회
  → Root·Branch 수직 탐색
  → Leaf 수평 탐색
  → 필요한 경우 ROWID Table Access

B-tree Index의 성능은 “Index를 사용했는가”로 결정되지 않습니다.

Index Access 비용
  ≈ Root→Leaf 탐색
   + 읽은 Leaf Block·Entry
   + 생성한 ROWID
   + 방문한 Table Block
   + 정렬 절감 효과
   + DML·공간·경합 유지비

이 이론의 범위

이 이론은 SQLP의 SQL 고급활용 및 튜닝 → 인덱스 튜닝 → 인덱스 기본 원리 범위에서 B-tree 구조와 ROWID 접근을 다룹니다. Clustering Factor, Table Access 최소화, Scan 효율화와 Index 설계는 후속 이론에서 더 깊게 다룹니다.

학습 목표

이 이론을 학습한 뒤에는 다음 내용을 설명할 수 있어야 합니다.

• Oracle 공식 B-tree 용어와 B*Tree 관용 표기의 관계를 설명한다.
• Root·Branch·Leaf Block의 역할을 구분한다.
• Branch Entry가 검색에 필요한 최소 Key Prefix와 Child Pointer를 저장하는 이유를 설명한다.
• 모든 Leaf가 같은 깊이를 유지하는 Balanced 구조를 설명한다.
• Tree Height와 Branch Level의 관계를 설명한다.
• 수직 탐색과 수평 탐색을 실행계획의 Index Scan과 연결한다.
• Unique·Nonunique Index Leaf Entry의 ROWID 정렬 차이를 설명한다.
• Extended Physical ROWID의 구성과 변경 가능성을 설명한다.
• IOT Secondary Index의 Logical ROWID와 Physical Guess를 설명한다.
• 모든 Key Column이 NULL인 Row가 일반 B-tree에서 제외되는 규칙을 복합 Index에 적용한다.
• Index-only Access와 Table Access by ROWID를 구분한다.
• TABLE ACCESS BY INDEX ROWID BATCHED의 목적을 설명한다.
• Index가 Full Scan보다 불리할 수 있는 조건을 설명한다.
• INSERT·DELETE·UPDATE가 B-tree Segment에 미치는 영향을 설명한다.

1. 인덱스가 해결하려는 문제

1억 건의 주문 중 특정 고객의 최근 주문 10건을 찾는다고 가정합니다.

SELECT order_id,
       order_date,
       amount
FROM   orders
WHERE  customer_id = :customer_id;

Index가 없으면 넓은 Table 범위를 읽어 조건을 평가하는 Plan을 고려할 수 있습니다. customer_id가 선두인 Index가 있으면 정렬된 Key 공간에서 검색 시작점을 찾은 뒤 필요한 범위만 읽을 수 있습니다.

Table Scan
  → 많은 Table Block에서 Predicate 평가

B-tree Index
  → 시작 Key 탐색
  → 조건 범위의 Leaf Entry
  → 필요한 ROWID Table Access

그러나 결과가 Table의 큰 비율이면 많은 Index Leaf와 Table Block을 모두 읽게 되므로 Full Scan이 더 효율적일 수 있습니다.

2. B-tree가 Balanced Tree인 이유

B-tree는 모든 Leaf Block이 자동으로 같은 깊이를 유지하는 균형 구조입니다.

                 Root
             /     |     \
         Branch  Branch  Branch
         /   \      |      /   \
       Leaf Leaf   Leaf   Leaf Leaf

Key가 한쪽 방향으로 계속 증가하더라도 일반 Binary Search Tree처럼 한쪽 경로만 무한히 길어지는 구조가 되지 않습니다. Block Split과 상위 구조 조정으로 검색 깊이를 균형 있게 유지합니다.

2.1 Height와 BLEVEL

Height
  = Root에서 Leaf까지 읽는 Block 수

Branch Level(BLEVEL)
  = Height - 1

예를 들어 Root→Branch→Leaf 세 Block을 통과하면 Height는 3, BLEVEL은 2입니다.

B-tree Height가 작다고 모든 Index Scan이 저렴한 것은 아닙니다. 시작 Leaf를 찾은 뒤 수천 개 Leaf Block을 수평 Scan하고 수백만 ROWID로 Table을 방문하면 그 비용이 훨씬 클 수 있습니다.

3. Root·Branch·Leaf Block

3.1 Root와 Branch

가장 위의 Branch Block을 Root라고 합니다. Branch Block은 다음 정보를 저장합니다.

• 하위 Index Block을 선택하기 위한 Key 경계
• Child Block Pointer
• 분기 결정에 필요한 최소 Key Prefix

Branch에 전체 Key를 반복 저장하지 않고 분기 결정에 필요한 최소 Prefix만 저장하면 한 Block에 더 많은 Entry를 수용할 수 있습니다.

Branch Entry
  → 최소 Key Prefix
  → 해당 범위의 Child Block 주소

3.2 Leaf

Leaf Block은 실제 Index Entry를 저장합니다.

• Indexed Column Value
• Heap Table Row를 찾기 위한 ROWID
• Key 순서의 정렬
• 왼쪽·오른쪽 Leaf Block과의 양방향 연결

Leaf Block A ⇄ Leaf Block B ⇄ Leaf Block C

양방향 연결 덕분에 Ascending·Descending 방향의 범위 Scan이 가능합니다.

4. Unique·Nonunique Leaf Entry와 ROWID

4.1 Nonunique Index

중복 Key를 허용하는 Nonunique Index에서는 ROWID가 Key의 일부처럼 정렬에 참여합니다.

(10, 3000, ROWID-A)
(10, 3000, ROWID-B)
(10, 3000, ROWID-C)

따라서 동일한 (deptno, sal) 값의 Row도 (Key, ROWID) 순서로 구분됩니다.

4.2 Unique Index

Unique Index는 동일 Key가 두 Row에 존재할 수 없습니다. Oracle 공식 구조 설명에서는 Unique Index Leaf의 Data가 Key 기준으로 정렬되고, ROWID는 Entry의 Key Data 영역에 저장되지만 Nonunique Index처럼 Key 자체의 정렬 구성요소로 취급되지는 않습니다.

Unique Index
  → Key로 최대 한 Row

Nonunique Index
  → Key + ROWID 조합으로 Entry 고유화

4.3 Index Unique Scan과 Range Scan

INDEX UNIQUE SCAN
  → Unique Index의 모든 Key Column에 Equality Predicate
  → 결과 ROWID 0개 또는 1개

INDEX RANGE SCAN
  → 선두 Key 조건으로 정렬 범위를 Scan
  → 결과 ROWID 0개·1개·여러 개 가능

5. 수직 탐색과 수평 탐색

수직·수평 탐색은 구조를 이해하기 위한 교육 용어이며 실행계획 Operation Name 자체는 아닙니다.

5.1 수직 탐색

Root와 Branch를 따라 조건에 맞는 시작 Leaf를 찾습니다.

CREATE INDEX emp_x1 ON emp(deptno, sal);

SELECT empno,
       ename,
       sal
FROM   emp
WHERE  deptno = 10
AND    sal >= 3000;

Root
  → deptno=10 범위의 Branch
  → (10,3000) 이상이 시작되는 Leaf

5.2 수평 탐색

시작 Leaf에서 Key 순서로 Entry를 읽습니다.

(10,3000) → (10,3200) → (10,4000) → ...

deptno=10 범위를 벗어나면 더 이상 정답이 없으므로 Scan을 종료할 수 있습니다. Oracle 공식 설명의 Index Range Scan은 Leaf의 연결 목록을 앞이나 뒤 방향으로 이동할 수 있습니다.

Range Scan 비용
  → 수직 탐색 깊이
  + Scan한 Leaf Block·Entry

6. Physical ROWID

Heap-Organized Table의 Extended Physical ROWID는 개념적으로 다음 정보를 포함합니다.

• Data Object Number
• Relative File Number
• Data Block Number
• Block 안의 Row Slot Number

ROWID
  → 어느 Data Object의
  → 어느 Relative File·Block에 있는
  → 몇 번째 Row Slot인가

Index에서 얻은 ROWID로 Table Row를 직접 찾습니다.

INDEX RANGE SCAN
  → ROWID
  → TABLE ACCESS BY INDEX ROWID

6.1 ROWID를 업무 Key로 사용하지 않는 이유

• ALTER TABLE ... MOVE
• Segment Shrink
• Partition 간 Row 이동
• Export·Import·재구성
• Delete 후 공간 재사용

등으로 물리 위치가 달라질 수 있습니다.

ROWID는 현재 물리 위치를 표현할 뿐 고객번호·주문번호 같은 업무 의미를 가지지 않습니다. 업무 식별자는 Primary Key·Unique Key로 설계합니다.

7. IOT의 Logical ROWID

Index-Organized Table(IOT)은 Primary Key B-tree Leaf에 Row Data를 저장합니다. 따라서 Heap Table처럼 별도 Table Segment의 고정 Physical ROWID로 Row를 가리키는 구조가 아닙니다.

IOT Secondary Index는 Primary Key 기반 Logical ROWID(UROWID)를 사용합니다.

IOT Secondary Index Entry
  → Secondary Key
  → Primary Key 기반 Logical ROWID
  → Physical Guess

Physical Guess는 Secondary Index 생성 시점 등의 물리 위치를 이용해 IOT Leaf에 빠르게 접근하기 위한 최적화 정보입니다. Row가 이동해 Guess가 오래돼도 Primary Key 기반 Logical ROWID는 유효합니다.

Guess가 유효
  → 예상 IOT Leaf로 직접 접근 시도

Guess가 오래됨
  → Primary Key를 이용해 IOT 탐색

8. B-tree의 NULL 저장 규칙

Oracle의 일반 B-tree Index는 모든 Index Key Column이 NULL인 Row를 저장하지 않습니다.

8.1 단일 Column

CREATE INDEX emp_comm_ix ON emp(comm);

comm IS NULL인 Row는 Key 전체가 NULL이므로 Entry가 없습니다.

8.2 복합 Index

CREATE INDEX emp_comm_ix2 ON emp(comm, empno);

empno가 NOT NULL이면 다음 Row는 저장됩니다.

(comm=NULL, empno=1001)
(comm=NULL, empno=1002)

전체 Index Key가 NULL이 아니기 때문입니다.

(NULL, NULL)
  → 일반 B-tree Entry 없음

(NULL, 1001)
  → Entry 있음

Bitmap Index는 전체 NULL Key도 저장할 수 있습니다. Cluster Key 관련 예외도 있으므로 이 이론의 일반 Heap Table B-tree 규칙과 구분합니다.

8.3 Index-only Scan의 NULL 주의

Index만으로 Table 전체 Row를 반환하는 Fast Full Index Scan을 고려할 때는 모든 Key가 NULL인 Row가 결과에서 빠지지 않는 조건이 필요합니다.

대표적으로 다음 중 하나가 있어야 합니다.

• Index Column 중 하나에 NOT NULL
• Predicate가 NULL Row를 결과에서 제외

9. Index-only Access와 Table Access

다음 Index를 가정합니다.

CREATE INDEX emp_x2 ON emp(deptno, sal, empno);

SELECT empno,
       sal
FROM   emp
WHERE  deptno = 10
AND    sal >= 3000;

조건과 반환 Column이 모두 Index에 있으면 Table을 방문하지 않을 수 있습니다.

INDEX RANGE SCAN EMP_X2

ename이 필요하면 Index에 없으므로 ROWID Table Access가 필요할 수 있습니다.

SELECT empno,
       ename,
       sal
FROM   emp
WHERE  deptno = 10
AND    sal >= 3000;

TABLE ACCESS BY INDEX ROWID EMP
  INDEX RANGE SCAN EMP_X2

Oracle B-tree에는 일부 DBMS의 INCLUDE와 동일한 비정렬 포함 Column 문법이 없습니다. 후행 Column을 추가하면 Index Key Entry의 일부가 되어 Segment 크기와 DML 유지비에 영향을 줍니다.

10. TABLE ACCESS BY INDEX ROWID BATCHED

다음 Plan은 Index에서 ROWID를 몇 개씩 모은 뒤 Table Block 순서에 가깝게 접근하려는 최적화입니다.

TABLE ACCESS BY INDEX ROWID BATCHED EMP
  INDEX RANGE SCAN EMP_X1

Index에서 ROWID Batch 수집
  → ROWID의 Table Block 위치 고려
  → 같은 Block 재방문 감소 시도

BATCHED는 반드시 하나의 Physical Multiblock Read로 Table을 읽는다는 뜻이 아닙니다. Cache Hit, Prefetch와 비동기 I/O가 결합될 수 있으므로 다음을 함께 봅니다.

• A-Rows
• Buffers
• Reads
• Physical Read Request
• Clustering Factor
• 최종 Row 수

11. Table Random Access와 Clustering

Index에서 많은 ROWID를 얻어도 이들이 적은 Table Block에 모여 있다면 Table Access가 상대적으로 효율적일 수 있습니다.

좋은 물리 배치
Index Key 순서
  → 비슷한 Table Block의 ROWID

반대로 ROWID가 넓은 Block에 흩어져 있으면 같은 범위 Scan에서 많은 I/O가 발생할 수 있습니다.

높은 Clustering Factor 방향
  → Index Key 순서와 Table Block 순서 불일치
  → 큰 Range Scan에서 반복·Random Block Access 증가

낮은 Clustering Factor 방향
  → 가까운 Key가 같은·인접 Table Block에 모임

Clustering Factor의 계산과 Table Access 최소화는 후속 이론에서 다룹니다.

12. Index가 Full Scan보다 불리할 수 있는 경우

Index 후보 10행
  → Table Block 5개
  → 결과 10행

Index 후보 1,000,000행
  → Table Block 600,000개
  → 결과 800,000행

두 번째 상황에서는 다음 비용이 겹칩니다.

• Index Root·Branch·Leaf 읽기
• 많은 ROWID 생성
• 흩어진 Table Block Access
• 넓은 결과 반환

Full Table Scan은 Multiblock·Direct Path 방식으로 Table을 순차적으로 읽을 수 있으므로 대량 조회에서는 더 효율적일 수 있습니다.

Index 사용
  ≠ 항상 적은 I/O

Full Scan
  ≠ 항상 나쁜 Plan

13. INSERT·DELETE·UPDATE와 B-tree 유지

13.1 INSERT

새 Key는 정렬 위치에 삽입됩니다. Leaf Block에 공간이 부족하면 Block Split이 발생할 수 있습니다.

Leaf 공간 부족
  → 새 Block 확보
  → Entry 분배
  → Branch Pointer 갱신

모든 INSERT가 Split을 만들지는 않습니다. Free Space, Key Pattern, 동시성에 따라 달라집니다.

13.2 DELETE

Delete된 Entry는 Transaction 일관성을 유지한 뒤 재사용 가능한 공간이 될 수 있습니다. Row를 삭제해도 Index Segment 크기가 즉시 줄어드는 것은 아닙니다.

13.3 UPDATE

Index Key Column이 변경되면 기존 Entry 삭제와 새 Entry 삽입이 필요합니다.

Index에 많은 후행 Column을 포함할수록 다음 비용이 증가할 수 있습니다.

• Segment 크기
• Buffer·Redo·Undo
• INSERT·UPDATE·DELETE 유지비
• Block Split·경합 가능성

14. 실행계획과 B-tree 구조 연결

SELECT /*+ GATHER_PLAN_STATISTICS */
       empno,
       ename,
       sal
FROM   emp
WHERE  deptno = 10
AND    sal >= 3000;

TABLE ACCESS BY INDEX ROWID BATCHED EMP
  INDEX RANGE SCAN EMP_X1

분석 순서입니다.

1. Index Key 순서와 선두 조건을 확인합니다.
2. Root·Branch 수직 탐색으로 시작 Leaf를 찾을 수 있는지 판단합니다.
3. Leaf를 어디까지 수평 Scan하는지 확인합니다.
4. Index Operation의 Starts, E-Rows, A-Rows, Buffers를 확인합니다.
5. 생성된 ROWID 수와 Table Access의 A-Rows·Buffers·Reads를 비교합니다.
6. Table 단계 Filter에서 대량 Row가 탈락하는지 확인합니다.
7. Index만으로 결과를 만들 수 있는지 확인합니다.
8. Clustering, 정렬 절감과 DML 유지비를 함께 평가합니다.

SELECT *
FROM TABLE(
  DBMS_XPLAN.DISPLAY_CURSOR(
    :sql_id,
    :child_no,
    'ALLSTATS LAST +PREDICATE +ALIAS +NOTE'
  )
);

15. 자주 혼동하는 판단

16. 최종 학습 프레임

1. Index Column 순서와 NULL 가능성은 무엇인가?
2. Unique인가 Nonunique인가?
3. Root·Branch가 어느 시작 Leaf로 안내하는가?
4. Leaf를 어느 방향으로 어디까지 읽는가?
5. 몇 Entry와 ROWID를 생성하는가?
6. Table Access가 필요한가?
7. ROWID가 몇 Table Block에 분산되는가?
8. 정렬·Top-N을 절감하는가?
9. 전체 조회에서는 Full Scan보다 유리한가?
10. DML·공간·경합 비용을 감수할 가치가 있는가?