데이터베이스 인덱스는 왜 B-tree를 사용하는가?
서론 - 인덱스에서 쓰이는 B tree가 뭔데?
Tree 구조는 기본적으로 탐색시 시간복잡도 O(log N)을 가진다.
하지만 최악의 경우, 트리 노드가 한쪽 방향으로 쏠려서 O(N)을 가지게 된다.
이런 경우를 방지하기 위해서 Balanced Tree를 이용한다.
balanced tree : 노드 삽입 및 삭제시 특정 규칙에 맞게 재정렬되어 양쪽 자식 수의 밸런스를 유지하는 트리
최악의 경우에도 각 연산이 무조건 O(log N)를 보장하며 redblack-tree나 b-tree가 여기에 해당한다.
본론 - 각 자료구조간 비교를 통해 확인해보자
데이터베이스의 인덱스에서는 위의 B tree와 B+tree 자료구조를 채택해서 사용하고 있다. 그렇다면 다른 자료구조도 많은데 왜 하필 저 녀석들을 사용할까?
각 자료구조간의 비교를 통해서 알아보자.
HashTable - 탐색 시간이 O(1)인데 인덱스로 사용하면 안돼?
가장 먼저 생각나는 조회 성능의 해시 테이블을 인덱스로 사용하는 경우를 상정하겠다.
해시 테이블은 단 하나의 데이터를 탐색하는데 걸리는 시간이 O(1)이라 탐색 시간은 자료구조 중에서 가장 빠르다.
하지만.. 인덱스 Id가 100보다 큰 record들을 모두 조회한다고 하면 해시 테이블이 무슨 수로 그 범위를 탐색할건가?
하나의 데이터를 찾는데 걸리는 시간이 O(1)이라도 이 범위에 해당하는 record들을 모두 가져오는데 몇 번의 탐색을 하게 될까? 과연 그 방식이 효율적이겠는가?
낱개로 각각의 데이터를 가져오기 때문에 비효율적일 수 밖에 없다.
RedBlack Tree - 같은 Balanced Tree인데 왜 안돼?
RedBlack-Tree와 B-Tree 비교를 통해서 왜 B-Tree를 사용하는지 알아보겠다.
노드의 삽입, 탐색, 삭제도 O(logN)으로 훌륭하고, Tree 구조의 불균형 문제도 해결해서 매력적이다.
하지만 무조건 각 노드마다 하나의 데이터만 가지므로 접근할때 참조 포인터로 접근해야한다.
하나의 노드에 여러 데이터(배열)를 저장하며, 항상 정렬된 상태로 존재한다.
같은 노드 공간의 배열 데이터들이 자식 노드처럼 참조 포인터로 접근할 필요가 없다.
각 노드마다 자식으로 여러 데이터(배열)을 가져서 승계시에만 참조 포인터를 이용하고, 동일 노드 내에서는 '정렬'된 상태라 트리 높이도 낮아서 결과적으로 노드 방문 수가 RedBlack-Tree보다 적다.
이는 대량의 데이터를 다루는 disk IO에서 더욱 효과적으로 인덱스로 쓰이게 된 이유이다.
Array - 배열을 사용하면 탐색 시간이 빠르지 않나?
배열을 인덱스로 사용하게 되면 아예 참조 포인터를 통해 자식 노드를 찾는 과정이 없어서 탐색이 B-Tree보다 빠르긴 하다.
근데 배열의 노드 삭제나 추가는 어떻게 감당하나?
훨씬 비효율적인 성능 문제가 발생하게 된다.
LinkedList - 배열의 삭제나 삽입 문제는 LinkedList로 해결되지 않는가?
LinkedList는 삽입, 삭제시 포인터를 끊고 추가될 요소 혹은 삭제할 요소를 처리한다.
배열은 정렬 상태로 만들어서 이진 탐색하기에 O(log N)의 빠른 탐색 시간을 보장한다.
LinkedList에서 정렬 상태를 어떻게 만들건가?
1. 정렬된 상태에 삽입하는 경우 : 탐색 O(N) + 삽입 O(1) → 시간복잡도 O(N)
이 경우, 매번 정렬된 상태를 만들기 위해 전체 탐색하는 과정이 비효율적이다.
2. 삽입시마다 전체 정렬해도 랜덤 접근이 불가능하기 때문에 시간복잡도 O(N logN)
결론 - 데이터베이스의 인덱스는 왜 B-Tree인가?
- 항상 정렬된 상태로 값 비교하는 부등호 연산에 문제가 없다 (↔ HashTable)
- 참조 포인터가 적어서 빠른 메모리 접근 가능 (↔ RedBlack Tree)
- 탐색뿐만 아니라 저장,수정,삭제도 항상 시간복잡도 O(log N) 유지 (↔ Array, LinkedList)
출처 및 인용 :
wikipedia
https://helloinyong.tistory.com/296