[딥 다이부] 이진트리, 이진탐색트리, B-Tree, B+Tree 개념과 꼬리질문

Q. 트리란 무엇인가?

A. 정의 : 부모 자식 관계로 이루어진 계층적 구조의 자료구조

 

Q. 이진 트리란 무엇인가?

A. 자식노드가 최대 2개로 이루어진 트리 형태의 자료구조를 의미한다.

이진 트리 : 리프노드를 제외하고, 자식노드가 2개로 이루어졌다.

Q. 이진 탐색 트리는 무엇인가?

A. 마찬가지로 자식노드가 최대 2개로 이루어진 트리 자료구조. 트리의 모든 노드는 정렬된 상태를 유지하는데, 특정 노드의 왼쪽 서브트리는 해당 노드보다 작은 값을 가지며, 오른쪽 서브트리는 해당 노드보다 모두 큰 값을 가진다.

 

이진 탐색 트리

 

 

힙(Heap)과 BST의 차이도 생각해보자

 

Q. 이진 트리와 이진 탐색 트리의 차이는 무엇인가?

A. 정렬 상태라 할 수 있다. 이진 탐색 트리는 정렬된 이진 트리로 볼 수 있는데, 노드의 왼쪽 하위 트리에는 해당 노드보다 작은 키가 있는 노드, 오른쪽 하위 트리에는 큰 키가 있는 노드만 포함된다.

 

Q. 이진 탐색 트리의 특징은 무엇인가?

A. BST는 중위 순회 (Inorder Traversal) 를 수행하며 모든 키를 정렬된 순서로 가져올 수 있다. 트리가 균형 상태라면 O(log N) 시간이 걸리지만 불균형 상태(선형)라면 O(N) 의 시간이 소요된다.

 

Q. 왜 이진 탐색 트리는 중위 순회로 정렬되는가?

A.  이진 탐색 트리의 특성을 생각해보자. 왼쪽 서브트리는 루트 노드보다 작고, 오른쪽 서브트리는 루트 노드보다 크기 때문인데, 중위순회로 BTS의 값을 나열하면 정렬된 상태임을 확인할 수 있다.

 

1 - 3 - 4 - 6 - 7 - 8 - 10 - 13 - 14

 

Q. 중위 순회란?

왼쪽 자식 노드를 갖지 않는 노드에  도달할 때까지 왼쪽 서브 트리로 내려간다. 해당 노드를 방문 후 부모 노드를 방문하고, 오른쪽 노드로 넘어가 다시 왼쪽 서브 트리를 찾아가는 재귀적 순회를 반복한다. 오른쪽 서브 트리가 존재하지 않으면 부모 노드를 방문하고 다시 오른쪽 노드의 왼쪽 서브트리를 탐색한다.

 

---

Q. B-Tree 란 무엇인가?

A. 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 수가 2보다 큰 트리를 의미.

대량 데이터의 저장 효율을 위해 DB 나 파일 시스템에서 주로 사용하는 자가 균형 탐색 트리 구조를 의미한다. 

 

 

Q. B-Tree 의 특징은 무엇인가?

데이터가 정렬된 상태로 유지되어 있다. 시간복잡도가 O(log N) 이란 점에서, 트리 내 모든 값에 대한 동일한 탐색시간을 갖는다. 이를 균일성이라 한다. 즉 루트 노드에서 모든 리프 노드로 가는 경로의 길이가 같다.

 

Q. 그럼 BST 는 균일하지 않은가?

BST와 B-Tree 의 결정적 차이는 트리의 높이라고 생각하는데, B-Tree 는 모든 리프노드의 높이가 동일하다. 즉 B-Tree의 리프노드는 모두 동일한 레벨에 존재하기 때문에 같은 시간복잡도를 갖지만, BST 는 최악의 경우 한쪽으로 치우친 선형의 트리가 만들어질 수 있고 이 경우 시간복잡도는 O(N) 이 될 수 있다.

 

Q. B-Tree 와 BST 의 차이는 무엇인가?

A. BST 는 하나의 노드에서 가질 수 있는 키 값이 하나지만, B-Tree 는 2개 이상 가질 수 있다. 또한 BST 는 최대 2개의 자식 노드만 가지지만, B-Tree 는 둘 이상의 자식 노드를 가질 수 있다. 이로인해 B-Tree 는 균일성이라는 특징을 가진다.

 

Q. 뭐하러 둘 이상의 key와 자식 노드를 가지나?

A. 일반적으로 B-Tree는 데이터를 디스크나 다른 보조 저장 장치에 효율적으로 저장하고 검색하는 경우에 사용된다. 한 노드가 가지는 key 가 많다면, 더 적은 디스크 액세스로 더 많은 데이터를 읽을 수 있기 때문에 효율적이다.

 

Q. 그렇다면 하나의 노드에 모든 key 를 저장하면 되지 않겠느냐?

A. 그럼 리스트와 다를게 없고, 선형탐색을 하기 때문에 트리를 사용하는 의미가 사라진다. 

 

Q. B-Tree 는 어떻게 균형을 유지하는가?

A. B-Tree 는 모든 리프노드가 동일한 레벨에 있고, 개별 노드가 가질 수 있는 key 의 개수가 특정 범위(min ~ max) 내에 있다. 임의의 노드가 너무 커진다면 key 가 재분산되거나 노드가 쪼개지고, 노드가 너무 작다면 다른 노드와 병합된다. 

 

Q. B-tree 의 조회 시간복잡도는 어떻게 되는가?

A. 시간복잡도는 O(log n) 이며, n 은 트리에 존재하는 key 의 개수를 의미한다. 

 

Q. B-tree 의 높이가 낮다는 건 어떤 의미인가?

A. B-Tree의 높이는 탐색/삽입/삭제 작업의 성능에 영향을 미치는데, 높이가 낮다는 것은  더 적은 Disk I/O로 작업이 이뤄질 수 있음을 의미한다. 쉽게 말해 높이가 낮을 수록 작업 속도가 더 빠르다.

 

Q. DB 인덱스가 B-Tree 인 이유는 무엇인가?

A. ㅈㄴ 빠르다

1. 모든 노드는 정렬된 상태로 저장되기 때문에, range 연산을 빠르게 처리할 수 있다.

2. 한 노드에 여러 key 가 존재하기에 전체적인 참조 포인터가 적어지는 효과가 있다. 

3. 데이터 탐색 뿐 아니라, 저장/수정/삭제에도 동일하게 O(log N) 시간복잡도를 가진다.

 

Q. B-Tree 와 B+Tree 의 차이는 무엇인가?

A. B+ 는 B-의 확장된 개념으로,모든 data가 leaf node 에 저장돼 있고, internal nodes 에는 leaf nodes 로 향하는 포인터(key)만 저장된다. 이는 빠른 디스크 IO 효과를 낸다.

 

Q. B-Tree에 비해 B+Tree 의 장점은 무엇인가?

A. 범위 탐색과 순차적 스캔이 더 빠르다. Fan out 의 차수가 높은데, 한번의 Disk I/O 작업으로 여러개의 key 에 접근할 수 있다. 

 

Q. B-Tree 와 B+Tree 의 풀스캔시 어떤 차이가 있는가?

B-Tree 는 모든 노드를 탐색해야 하는 반면, B+Tree 는 리프 노드만 탐색하면 된다. 

 

Q. B-Tree 와 B+Tree 중 어느것이 DB 인덱스로 적합한가

A. DB 인덱스 생성엔 B-Tree 와 B+Tree 모두 사용되지만, B+Tree 의 이점 덕분에 더 자주 사용된다.

B+Tree 는 모든 키가 리프 노드에 저장되고, 리프 노드는 Linked List 로 연결되어 Range Query 에 대해 효율적으로 탐색할 수 있다. B+Tree 의 내부 노드는 키를 저장하지 않고 자식 노드를 가리키는 포인터만 저장하기에 Disk I/O 성능이 더 우수하다. 

 

 

* Degree (차수) 와 Fan-out 추가설명