> For the complete documentation index, see [llms.txt](https://real-dev.gitbook.io/real-library/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://real-dev.gitbook.io/real-library/real-post/.-index-range-scan.md).

# 화두. Index Range Scan의 시간복잡도는 몇인가

최근 RDBMS의 Index에서 Index Range Scan 시, 특정 레코드를 찾는데 걸리는 시간 복잡도에 관한 문제를 받았는데 그 때 낸 답변이 아무래도 틀린 것 같아 다시 정리해보았으며 출제된 문제는 아래와 같다.

* 총 N개의 row가 입력된 학생 성적 테이블을 기준으로
* 학생ID, 국어 성적, 영어 성적, 수학 성적 (각 0\~100점)으로 구성된 인덱스에서
* **국어 성적이 50점 이상인 학생 중, 가장 점수가 낮은 학생을 찾는 쿼리가 발생했을 때** 이 인덱스의 탐색 시간 복잡도는 몇인가?

이에 나는 인덱스 선두 컬럼은 국어이며, 이를 기준으로 인덱스가 정렬되어 있기 때문에 순차 탐색할 경우 최악의 시간 복잡도는 O(N)이라고 답했는데 두고두고 바보같은 대답이라 다시 풀어보았다.

***

### N이 상수일 경우

문제에서 N은 무수히 증가할 수 있는 양의 정수지만, 일단 계산을 용이하게 만들기 위해 몇 가지 가정을 세워보자.

* RDBMS는 Mysql이며, 엔진은 InnoDB를 사용한다.
* 인덱스 노드의 크기는 Mysql의 페이지 기본값인 16KB이다.
* 인덱스는 `BIGINT` 1개 (학생 ID, 8byte), `UNSIGNED INT(3`**)** 3개(국영수 성적, 4byte) 로 이뤄져있다. 또한 자식 노드를 지목하기 위한 포인터로 6byte를 할당하여, 인덱스 레코드 당 26byte를 차지한다.
* 각 인덱스 컬럼은 오름차순으로 정렬되어 있다.

위의 가정에서 국어 성적이 50이상인 학생을 조회하기 위해선 인덱스 브랜치 노드 중 최종 계층에서, 국어 점수가 50점 이상인 레코드(LIMIT 1)를 발견하고, LIMIT 1의 직전 레코드부터 인덱스 리프 노드 탐색을 시작해야한다.

즉, 인덱스 브랜치 노드 탐색 시간 + 인덱스 리프 노드 탐색 시간이 최종적인 레코드 탐색 시간이 된다.

이 때 인덱스 리프 노드의 탐색 시간 복잡도는 최종 인덱스 브랜치 노드에 속한 레코드들 사이의 거리 (R)과 일치한다. 모든 레코드가 인덱스 브랜치 노드에 속해있는 것은 아니며, 이는 최종 계층의 인덱스 브랜치 노드에서도 마찬가지이기 때문. 즉, 테이블의 데이터들은 일정한 간격 (R)을 두고 인덱스 브랜치 노드에 포함되어 있다고 할 수 있다.

이 때 **R은 인덱스 레코드의 크기가 결정된 시점에서 불변하는 상수 S (16KB/ 인덱스 레코드 크기))보다 항상 작다.** (만약 R이 S보다 커지게 되면 B-Tree의 깊이가 증가하고 재정렬이 이뤄지기 때문에)\*\*\*\*

따라서 Index Range Scan으로 인해 **인덱스 리프 노드에서 발생하는 탐색 시간은 N/ S ^(Depth-1)이 된다.**

인덱스 브랜치 노드를 탐색하는데 걸리는 시간을 계산해보자면, 가장 면저 인덱스 노드에 속하는 레코드의 길이 S과 인덱스를 구성하는 B-Tree의 깊이가 필요하다. 이 때 S은 각 인덱스 노드 페이지의 크기를 인덱스 레코드의 크기로 나누어 구할 수 있다.

즉 위의 가정에 따르면 S은

$ 16 \* 1024 byte/ 26 byte $

(8 byte (학생 ID) + 4 byte+4 byte+4 byte (국영수 성적)+6 byte(자식 노드의 주소))

최종적으로 약 630개가 된다.

그 말은 결국 학생 성적 레코드의 수가 630개를 초과하지 않는 상황. 즉 N이 630보다 작은 상황에선 인덱스 트리의 깊이가 1이며, 이 때의 인덱스 브랜치 노드 탐색의 시간 복잡도는 O(1)이다. (N이 630이하로 수렴된 상태이기 때문)

그렇다면 학생 성적 레코드의 갯수 N이 좀 더 큰 수 일 때를 감안하면 어떨까? 예컨데 교육청에서 가지고 있는 학생 성적 인덱스에서 국어 성적이 50점 이상인 경우를 찾는다면?

이 때의 레코드 갯수를 50,000,000개 (5천만)라 가정해보겠다. 그렇다면 B-Tree의 깊이는 3이 된다.

* Index Root Node에서 630개의 레코드를 수용한다면, 레벨 2에선 630\*630 즉, 396,900개의 레코드를 수용할 수 있다. 레벨 3에선 다시 630^3 (250,047,000)개의 레코드를 포함할 수 있다. 이는 레코드의 수 50,000,000보다 크며, 따라서 해당 인덱스의 총 깊이는 3이 된다.

이 때 최악의 상황을 가정하기 위해 가장 높은 국어성적이 50점이라고 가정해보겠다.

논리적으로 인덱스 탐색 과정을 설명하면, 인덱스 브랜치 노드를 1번 탐색할 때마다 길이가 630인 리스트를 1회 순회해야하며, 이를 2회 반복해야 한다 (인덱스 리프 노드 탐색을 제외해야 하기 때문에). 그리고 최종적으로 인덱스 리프 노드를 탐색해야하기에 R 길이의 리스트를 추가로 1회 탐색해야한다.

* 이 때 R은 약 125이다. R은 50,000,000 / 630^(Depth - 1)이기 때문.

즉, 50,000,000개의 레코드가 존재하는 인덱스에서 국어 점수가 50점 이상인 레코드 중 국어 점수가 가장 낮은 레코드를 찾기위해선 최대 약 (630 \* 2 + 125)번의 연산이 필요하다고 볼 수 있다.

이를 관계식으로 나타내면 Index Range Scan을 통한 특정 레코드를 탐색하는 과정은

$ S \* B-Tree Depth + R $

```
*S: 인덱스 브랜치 노드의 최대 길이

*R: 깊이가 가장 깊은 인덱스 브랜치 노드에 포함된 레코드 간의 거리
```

으로 나타낼 수 있다.

***

### Big-O 시간 복잡도 계산

각 인덱스 노드의 최대 길이 S은 인덱스 레코드의 크기가 결정되었을 때 정해지는 상수다. 위 예시에선 630이었으며, 이는 N의 증감과 무관하다.

→ 16KB/Index record size = **S**

B-Tree의 깊이 Depth는 S ^ Depth가 N보다 커지는 수 중 가장 작은 양의 정수이다. 즉 S은 log Depth의 N보다 언제나 크며, log(Depth-1)의 N보다는 항상 작다.

* $ log Depth의 N ≤ S < log (Depth-1)의 N $

즉 인덱스 브랜치 노드를 모두 탐색하는데 연산 (S \* Depth)의 시간 복잡도는 $ log (Depth-1)의 N \* Depth $로 나타낼 수 있으며, **이는 Big-O 표기법에 따라** $ O(log N) $**이 된다.**

Index Range Scan 시, 인덱스 리프 노드를 탐색하는데 걸리는 시간 R은 언제나 S보다 작다(R이 S보다 같거나 커지는 경우엔 Depth가 증가하며 인덱스가 재정렬된다).

따라서 인덱스 리프 노드 스캔의 시간 복잡도는 최악의 경우에도 O(S)보다는 작음을 보장할 수 있고, 최종적으로 O(1)으로 표기할 수 있다.

따라서, 시간 복잡도 Big-O 표기로 나타냈을 때

국어 성적이 50 이상이며, 그 중 가장 작은 레코드를 인덱스 리프 노드에서 찾는 연산의 최종적인 시간 복잡도는

**O(log N + 1) ⇒ O(log N)이 된다.**