Q. Mysql InnoDB는 왜 이진트리가 아닌 Balanced Tree를 사용할까??
Q. 자바의 Tree 자료타입은 왜 Balanced Tree가 아닌 균형이진탐색 트리인 RB 트리를 사용할까??
이진트리를 학습하며 나는 위와 같은 궁금증이 생겼다.
따라서 나는 이진트리, 이진탐색트리, 완전이진트리와 mysql innoDB의 balanced tree를 비교하며 어떠한 기준으로 자료구조가 선택됬는지 알아보았다.
내가 알아본 기준은 아래와 같다.
[InnoDB에서 Balanced-Tree 사용하는 이유]
- 균형 유지
- Fan-Out에 따른 탐색 횟수
- 범위 검색
[자바의 Tree 타입이 균형이진탐색 트리 사용하는 이유]
- 메모리와 디스크의 차이
- 단순한 구조와 쉬운 구현
균형유지
우선 이진트리나 이진탐색트리와 Balanced-Tree를 비교하면 균형 유지에서 차이를 보인다.
이진트리와 이진탐색트리는 편향된 트리가 나올 수 있기 때문에 시간복잡도가 최악의 경우 O(N)이 나올 수 있어 조회 성능에 좋지 못하다.
그럼 이제 이진트리와 이진탐색트리는 조회성능에 좋지 못하므로 제외하고,
균형 완전이진트리인 힙과 균형 이진탐색트리인 RB트리와 비교할 수 있다.
Fan-Out에 따른 탐색횟수
균형 완전이진트리나 균형 이진탐색트리 모두 이진트리이기 때문에 Fan-Out(분기 수)은 2이다.
Balanced-Tree는 부모 노드 하위에 여러개의 자식 노드를 가질 수 있다.
그리고 이 자식노드는 여러개의 레코드 키값으로 이루어져있다.
Balaced-Tree에서 여러 자식 노드 중 원하는 노드를 찾기 위해 이진탐색을 수행하지만,
하나의 key 노드가 여러 레코드의 key를 관리하므로 이진 탐색 트리와 비교하면 탐색에 몇단계를 건너 뛸 수 있다.
이러한 차이는 메모리와 디스크 위치에서 큰 차이를 나타낼 수 있다.
데이터를 주소를 알고 있다면 빠르게 접근 가능한 메모리와 다르게 디스크는 임의의 위치에 존재하는 데이터 접근 속도가 상대적으로 느리다.
따라서 탐색을 몇단계 건너 뛰는 것은 메모리에서도 효율을 가져다주기는 하지만 디스크에서는 더 큰 효율을 가져다 줄 수 있기에 큰 차이를 나타낸다.
일반적으로 RDB의 설계의 주요 목적 중 하나가 조회 성능 향상을 위해 디스크 IO 작업을 줄이는 것에 초점이 맞춰져 있기에
균형 이진트리보다 Balanced-Tree가 적절한 자료구조가 될 수 있다.
범위 검색
Balanced-Tree의 모든 데이터를 리프노드에 존재한다.
중간에 존재하는 노드에는 key값만 할당되어 있다.(인덱스 역할만 수행)
그리고 리프노드는 LinkedList와 같이 참조관계를 통해 각 노드(데이터페이지)가 연결되어있다.
우리가 탐색하려는 대상의 시작 위치에 도달한다면 끝 지점까지 순차 탐색을 수행할 수 있다.
이진탐색처럼 분기과정을 재귀적으로 반복 호출하는 과정 없이 리프노드에 도달하면 순차 접근이 가능해진다.
Q. Mysql InnoDB는 왜 이진트리가 아닌 Balanced Tree를 사용할까??
- 균형 유지
- Fan-Out에 따른 탐색 횟수
- 범위 검색
위 3가지 측면을 비교해보니 innoDB에서 Balanced-Tree를 사용하는 이유에 대해 이해가 된다.
하지만 위 3가지 측면만 보면 Balanced-Tree가 모든 경우에서 더욱 좋아보는데 왜 java의 Tree 데이터 타입은 균형 이진탐색트리를 사용할까??
메모리와 디스크의 차이
DB에서 사용되는 자료구조는 저장공간 보다 우선시 되는게 조회 성능이다.
Balanced-Tree의 리프노드를 제외한 노드들은 실제 데이터가 존재하지 않고 key값만 저장되고 있다.
이는 저장공간은 낭비할 수 있지만, Fan-Out(분기)을 늘려 트리의 높이를 낮게하여 디스크의 I/O 부하를 줄이는 효과를 가져다 준다.
하지만 자바의 Tree 자료 타입은 메모리 공간에서 사용된다.
메모리는 디스크에 비해 상대적으로 크기가 작다.
대신에 데이터의 랜덤 접근에 빠른 성능을 보인다.
균형이진탐색트리는 이미 O(logN)이라는 충분히 빠른 조회 성능을 나타내기에 여기서 더 빠른 조회 성능 보다는
저장 공간의 효율에 초점을 두고 많은 공간이 필요로한 Balanced-Tree보다는 균형이진탐색트리를 사용하는 것이다.
단순한 구조와 쉬운 구현
균형 이진탐색트리는 메모리 공간에서 충분히 좋은 성능을 내고, 저장공간마저 효율적으로 사용하는데 구현까지 상대적으로 쉽다.
또한 이진탐색트리는 '두개의 분기만 존재하고 왼쪽은 작고, 오른쪽은 크다'라는 비교적 간단한 규칙을 갖고 있기에 구조가 단순하다.
단순한 구조와 쉬운 구현은 개발에 용이함을 가져다 주기에 해당 자료구조를 사용하지 않았나 싶다.
'자료구조 & 알고리즘 > 자료구조' 카테고리의 다른 글
| Map과 Set이란(Hash, Tree 기반 자료형 비교) (0) | 2025.06.12 |
|---|---|
| 레드블랙트리 (0) | 2025.05.30 |
| 이진탐색트리 - AVL 트리 (0) | 2025.05.30 |
| 완전이진트리 - 힙 (0) | 2025.05.29 |
| 비선형 자료구조 - 트리 (0) | 2025.05.29 |
