데이터베이스 인덱스 테이블을 구현할 때 트리 구조의 B+Tree와 B-tree 인덱스 방식을 많이 사용한다.
B tree의 시간 복잡도는 O(log N)으로, B tree 인덱스를 사용하면 데이터의 삽입, 갱신, 삭제 등에 드는 작업 비용을 줄일 수 있기 때문이다. 그런데 균형 이진 탐색 트리인 AVL Tree와 Red-Black Tree도 시간 복잡도 O(log N)으로, B Tree와 시간 복잡도가 동일하다.
B 트리의 시간 복잡도 O(log N)
균형 이진 탐색 트리 시간 복잡도 O(log N)
둘 다 O(log N)인데 왜 균형 이진 탐색 트리가 아닌 B 트리 계열을 인덱스로 사용하는 걸까?
잠시 컴퓨터 구조를 살펴보도록 하자.
CPU(Central Processing Unit, 중앙 처리 장치)는 '컴퓨터의 뇌' 역할을 하며, 컴퓨터에서 프로그램을 실행하는 데 필요한 연산을 처리하고 수행한다.
휘발성 메모리인 Main memory(RAM)은 실행 중인 프로그램의 코드들과 코드 실행에 필요한, 혹은 그 결과로 나온 데이터들이 상주한다.
비휘발성 메모리인 Secondary storage(SSD, HDD)는 프로그램과 데이터가 영구적으로 저장되는 곳으로, 실행 중인 프로그램의 데이터 일부가 임시 저장되는 곳이다.
데이터베이스는 영구적으로 데이터를 저장해야 하므로 Secondary storage에 위치하게 된다.
Secondary storage의 특징
- 데이터를 처리하는 속도가 가장 느리다.
- 데이터를 저장하는 용량이 가장 크다.
- block 단위로 데이터를 읽고 쓴다.
- block : file system이 데이터를 읽고 쓰는 논리적인 단위
- block의 크기는 2의 승수로 표현되며 대표적인 block size는 4KB, 8KB, 16KB 등이 있다.
DB 관점에서
DB는 영구적으로 데이터를 저장해야 하므로 Secondary storage에 저장된다.
그렇다면 DB는 실질적으로 어떻게 동작할까?
핵심이 되는 데이터들은 Main memory에 로드해두고, 나머지 데이터는 Secondary storage에 보관한다.
외부에서 요청이 들어오게 되면 그 요청이 Main memory에 있는 데이터들로만 처리할 수 있는지 확인한다.
만약에 Main memory에 있는 데이터들로만 처리할 수 있으면 처리를 하고,
Main memory에 필요한 데이터가 없다면 Secondary storage에서 데이터를 block 단위로 읽어와서 Main memory에 로드한 후 데이터를 처리한다.
→ DB에서 데이터를 조회할 때 Secondary storage에 최대한 적게 접근하는 것이 성능 면에서 좋다.
그렇다면 위의 테이블에서 n 컬럼을 조회한다고 해보자.
빠른 조회를 위해 n컬럼에 대해 인덱스를 생성하는데, 비교를 위해 B Tree 인덱스와 AVL Tree 인덱스를 생성하도록 하자.
AVL Tree 인덱스 vs B Tree 인덱스
- tree의 각 노드는 서로 다른 block에 있다고 가정
- 초기에는 root 노드를 제외한 모든 노드는 Secondary storage에 있다고 가정
- 초기에는 데이터 자체도 모두 Secondary storage에 있다고 가정
- n이 5인 데이터를 조회해보자.
AVL Tree 인덱스 사용할 경우
5와 6을 비교했을 때 5가 6보다 작기 때문에 왼쪽 노드로 이동한다.
Secondary storage에서 노드 3에 대한 데이터를 읽어와서 Main memory에 올린 후 5와 3을 비교한다.
5가 더 크기 때문에 오른쪽으로 이동한다.
Secondary storage에서 노드 4에 대한 데이터를 읽어와서 Main memory에 올린 후 5와 4를 비교한다.
이번에도 5가 더 크기 때문에 오른쪽으로 이동한다.
Secondary storage에서 노드 5에 대한 데이터를 읽어와서 Main memory에 올린다.
이때 5를 찾았기 때문에 인덱스 조회는 끝났고 포인터가 가리키고 있는 데이터를 읽어와야 한다.
마지막으로 Secondary storage에서 데이터를 읽어서 Main memory에 올린 후, 데이터를 가공해서 요청에 대해 응답한다.
AVL Tree 인덱스를 사용하면 이렇게 총 4번 Secondary storage에 접근하게 된다.
B Tree 인덱스 사용할 경우
5차 B Tree를 사용한다고 가정해 보자.
먼저 루트 노드에서부터 살펴본다. 항상 오름차순으로 정렬되어 있으므로 왼쪽부터 본다.
4는 5보다 작으므로 오른쪽으로 가서 8과 5를 비교한다. 이때 5는 8보다 작으므로 4와 8 사이에 있는 노드로 이동한다.
Main memory에 해당 노드가 없으므로 Secondary storage에서 노드를 읽어서 Main memory에 올려준다.
이제 마찬가지로 왼쪽부터 확인을 해준다. 이때 5를 발견하면 인덱스 탐색은 끝이다.
이제 5에 대한 데이터를 Secondary storage에서 읽어서 Main memory에 로드한다.
이렇게 B Tree 인덱스를 사용할 경우 Secondary storage에 총 2번 접근하게 된다.
결과 비교
| B Tree 인덱스 | AVL Tree 인덱스 | |
| storage 접근 횟수 | 2번 | 4번 |
| 자녀 노드 수 | 3~5개 | 1~2개 |
| 노드의 데이터 수 | 2~4개 | 1개 |
5차 B Tree에서 각 노드는 3~5개의 자녀 노드를 가질 수 있다. 반면에 AVL Tree는 각 노드에서 가질 수 있는 자녀 노드의 개수는 1~2개이다. 때문에 B Tree는 데이터를 찾을 때 더 빨리 탐색 범위를 좁혀나갈 수 있다.
또한 AVL Tree에서 각 노드는 1개의 데이터를 가질 수 있지만, B Tree에서는 각 노드가 2~4개의 데이터를 가질 수 있으므로 특정 노드를 읽어올 때 연관된 데이터를 효율적으로 읽어올 수 있다. 이로 인해 B Tree의 경우 block 단위 저장 공간 활용도가 더 좋아진다.
B Tree 살펴보기
B Tree의 성능을 더 자세히 알아보기 위해 이번에는 101차 B Tree를 살펴보도록 하자.
101차 B Tree는
- 최대 자녀 수 : 101
- 최대 Key 수 : 100
- 최소 자녀 수 : 51
- 최소 Key 수 : 50
를 가질 수 있다. (leaf, root 노드 제외)
먼저 worst case를 살펴보자. (worst case는 데이터를 최소한으로 가질 때를 의미)
이때 이 트리 전체의 데이터 개수를 계산해 보면, 약 26만 개의 데이터를 저장할 수 있음을 알 수 있다.
이번에는 best case를 보자. (best case는 데이터를 최대로 가질 때를 의미)
best case일 때 데이터 개수를 계산해 보면, 약 1억 개의 데이터를 저장할 수 있다.
26만 개 < 전체 데이터 수 < 1억 개
그렇다면 지금까지의 내용을 바탕으로 B Tree는 4개의 레벨만으로 수백만 ~ 수천만 개의 데이터를 저장할 수 있다.
즉, root 노드에서 가장 멀리 있는 데이터도 3번의 이동만으로 접근할 수 있고, 그만큼 Secondary storage에도 적게 접근할 수 있어서 성능 면에서 엄청난 이점을 가질 수 있다.
따라서 B Tree는 굉장히 많은 양을 저장해야 하는 데이터베이스에서 인덱스로 쓰기에 매우 적합한 자료구조다.
결론
- DB는 기본적으로 Secondary storage에 저장되기 때문에 같은 기능을 수행하더라도 Secondary storage에 최대한 적게 접근하는 것이 좋다. (Secondary storage는 데이터 처리 속도가 가장 느리기 때문)
- B Tree 인덱스는 균형 이진 탐색 트리에 비해 Secondary storage 접근을 적게 할 수 있다.
- B Tree는 노드에 여러 개의 데이터를 저장할 수 있으므로 block 단위의 저장 공간을 알차게 사용할 수 있다.
[Reference]
'Development > 데이터베이스' 카테고리의 다른 글
| JPA, Spring Data JPA 차이점 (0) | 2025.07.11 |
|---|---|
| JPA와 MyBatis (0) | 2024.12.13 |
| Redis (0) | 2024.12.04 |
| RDB와 NoSQL (0) | 2024.11.23 |