Ch07. 인덱스 - 트리 자료 구조

인덱스가 어떤 방식으로 데이터를 빠르게 검색하는지 이해하려면 먼저 트리 자료 구조를 알아야 한다.

트리 자료구조

• 트리는 부모 노드와 자식 노드로 구성된다.
  • 여기서는 각 원이 노드다. 노드 안에는 데이터와 다음 노드들의 위치가 보관된다.
• 가장 높은 조상을 루트(root)라 한다. (이 그림을 뒤집어보면 왜 트리라고 하는지, 처음을 루트라고 하는지 이해가 될 것이다.)
• 자식이 2개까지 올 수 있는 트리를 이진트리라 한다.
• 여기에 노드의 왼쪽 자손은 더 작은 값을 가지고, 오른쪽 자손은 더 큰 값을 가지는 것을 이진 탐색 트리라 한다.

이진 탐색 트리 - 입력 예시

이진 탐색 트리의 핵심은 데이터를 입력하는 시점에 정렬해서 보관한다는 점이다. 그리고 작은 값은 왼쪽에 큰 값은 오른쪽에 저장한다. 데이터 (10, 5, 15, 1, 6, 11, 16)을 순서대로 저장한다고 가정해 보자

1) 10 입력 후, 5, 15 입력

5입력

15 입력

• 5 저장(5는 10보다 작으므로 왼쪽에 저장)
• 15 저장(15는 10보다 크므로 오른쪽에 저장)

2) 1, 11, 6 저장

6 저장

1, 11 저장

• 1 저장: 1은 10보다 작다. 따라서 왼쪽으로 찾아간다. 1은 5보다 작다 따라서 왼쪽에 저장된다.
• 6 저장: 6은 10보다 작다. 따라서 왼쪽으로 찾아간다. 6은 5보다 크다. 따라서 오른쪽에 저장된다.
• 11 저장: 11은 10보다 크다. 따라서 오른쪽으로 찾아간다. 11은 15보다 작다. 따라서 왼쪽에 저장된다.

3) 16 저장

16 저장

• 16 저장: 16은 10보다 크다. 따라서 오른쪽으로 찾아간다. 16은 15보다 크다. 따라서 오른쪽에 저장된다.

 

이진 탐색 트리 - 검색

이진 트리 탐색 검색

• 여기에는 총 15개의 데이터가 들어있다. 여기서 숫자 35를 검색한다고 가정해 보자.
  1. 루트인 20과 35를 비교한다. 35가 더 크므로 오른쪽으로 찾아간다.
  2. 40과 35를 비교한다. 35가 더 작으므로 왼쪽으로 찾아간다.
  3. 30과 35를 비교한다. 35가 더 크므로 오른쪽으로 찾아간다.
  4. 노드에 있는 값을 비교한다. 35와 같으므로 35를 찾는다.
• 데이터가 총 15개인데 단 4번의 계산만으로 필요한 결과를 얻을 수 있었다.

이진 탐색 트리 계산의 핵심은 한 번에 남은 절반을 날린 다는 점이다. "계산을 단순화하기 위해 16개의 데이터가 있다"고 가정하자

• 16개의 데이터가 있다. 루트에서 처음 비교를 통해 절반의 데이터를 찾지 않아도 된다. 따라서 (16 / 2 = 8)이 된다.
• 8개의 데이터가 있다. 비교를 통해 절반의 데이터만 남는다. 따라서 (8 /2 = 4)가 된다.
• 4개의 데이터가 있다. 비교를 통해 절반의 데이터만 남는다. 따라서 (4 / 2 = 2)가 된다.
• 2개의 데이터가 있다. 비교를 통해 절반의 데이터만 남는다. 따라서 (2 / 2 = 1)이 된다.
• 1이 남았으므로 이 값이 맞는지 확인하면 된다.

이진 탐색 트리의 빅오 - O(logN)

16개의 경우 단 4번의 비교 만으로 최종 노드에 도달할 수 있다. 이것을 정리하면 다음과 같다.

• 2개의 데이터 => 2로 1번 나누기, log₂(2)=1
• 4개의 데이터 => 2로 2번 나누기, log₂(4)=2
• 8개의 데이터 => 2로 3번 나누기, log₂(8)=3
• 16개의 데이터 => 2로 4번 나누기, log₂(16)=4
• 32개의 데이터 => 2로 5번 나누기, log₂(32)=5
• 64개의 데이터 => 2로 6번 나누기, log₂(64)=6
• ...
• 1024개의 데이터 => 2로 10번 나누기, log₂(1024)=10
• 16,384개의 데이터 => 2로 14번 나누기, log₂ (16384)=14
• 65,536개의 데이터 => 2로 16번 나누기, log₂ (65536)=16
• 131,072개의 데이터 => 2로 17번 나누기, log₂ (131072)=17
• 1,000,000개의 데이터 => 2로 약 20번 나누기, log₂ (1,000,000)≈19.93
• 10,000,000개의 데이터 => 2로 약 24번 나누기, log₂ (10,000,000)≈23.22
• 100,000,000개의 데이터 => 2로 약 27번 나누기, log₂ (100,000,000)≈26.57

1024개의 데이터를 단 10번의 계산으로 원하는 결과를 찾을 수 있다. 데이터의 크기가 늘어나도 늘어난 만큼 한 번의 계산에 남은 절반을 날려버리기 때문에 데이터의 크기가 클수록 효과적이다. 1억 개의 데이터가 있어도 약 27번이면 원하는 데이터를 찾을 수 있다!

 

이게 가능한 이유는 데이터를 정렬한 상태로 보관하기 때문이다. 만약 정렬한 상태가 아니라면 이런 조회 방식은 불가능하다.

 

이진 탐색 트리 - 순회

이진 탐색 트리의 핵심은 입력 순서가 아니라, 데이터의 값을 기준으로 정렬해서 보관한다는 점이다. 정렬해서 보관했기 때문에 정렬된 순서로 데이터를 차례로 조회할 수 있다. (순회할 수 있다.)

 

데이터를 차례로 순회하려면 중위 순회라는 방법을 사용하면 된다. 왼쪽 서브트리를 방문한 다음, 현재 노드를 처리하고, 마지막으로 오른쪽 서브트리를 방문한다. 이 방식은 이진 탐색 트리의 특성상, 노드를 오름차순(숫자가 점점 커짐)으로 방문한다

 

데이터 중위 순회( 1, 5, 6, 10, 11, 15, 16 )

• 중위 순회 순서
  • 10의 기준에서 왼쪽 서브트리를 방문한다.
    • 5의 기준에서 왼쪽 서브트리를 방문한다.
      • 1을 출력한다.
    • 5 자신을 출력한다.
    • 5의 기준으로 오른쪽 서브트리를 방문한다.
      • 6을 출력한다.
  • 10 자신을 출력한다.
  • 10의 기준에서 오른쪽 서브트리를 방문한다.
    • 15의 기준에서 왼쪽 서브트리를 방문한다.
      • 11을 출력한다.
    • 15 자신을 출력한다.
    • 15의 기준으로 오른쪽 서브트리를 방문한다.
      • 16을 출력한다.

순서대로 오름차순인 (1, 5, 6, 10, 11, 15, 16)이 출력된 것을 확인할 수 있다.

참고로 자신의 오른쪽 노드부터 순회하면 반대로 내림차순인 (16, 15, 11, 10, 6, 5, 1 )순으로 출력할 수 있다.

 

밸런스 트리(Balanced Tree)

이진 탐색 트리의 검색, 삽입, 삭제의 평균 성능은 앞서 살펴본 것처럼 "O(log n)"이다. 하지만 트리의 균형이 맞지 않으면 최악의 경우 풀 테이블 스캔과 같은 O(n)의 성능이 나온다. O(n)은 "10개"의 데이터가 있다면 최악의 경우 "10"번의 탐색이 필요하다는 뜻이다.

 

만약 데이터를 1, 5, 6, 10, 15 순서로 입력했다고 가정해보자.

B 트리 단점(Table Full Scan과 동일)

• 이 경우 추가하는 값이 계속 오른쪽으로 입력된다.
• 이렇게 오른쪽으로 치우치게 되면, 결과적으로 15를 검색했을 때 데이터의 수인 "5"만큼 검색을 해야 한다.
• 이것은 성능상 풀 테이블 스캔과 같다! 이처럼 최악의 경우 O(n)의 성능이 나온다.

이진 탐색 트리 개선

B 트리

• 예를 들어 앞서 본 트리에서 중간에 있는 6을 기준으로 다시 정렬한다.
• 이렇게 균형을 유지하는 트리를 밸런스 트리(Balanced Tree)라고 한다.
• 대부분의 관계형 데이터베이스는 인덱스에 밸런스 트리를 사용해서 균형을 유지한다. 따라서 최악의 경우에도 O(log n)의 성능을 제공한다.

 

실제 인덱스에 사용되는 트리

인덱스는 트리 구조를 사용하기 때문에 정렬된 상태로 저장된다.

 

예를 들어 "item_name" 컬럼을 기준으로 인덱스를 만들면 다음과 같이 "item_name" 컬럼이 정렬된 상태로 저장된다. 그리고 인덱스에는 인덱스에 사용할 값(item_name)과 원본 데이터의 위치가 하나의 쌍으로 저장된다. 이전에 보았던 트리 구조에서 "item_name"과 원본 데이터의 위치를 함께 보관한다고 생각면 된다.(물론 트리 구조에 데이터를 보관하기 위해 비교할 때는 "item_name" 컬럼만 사용한다.)

 

• 대부분의 주요 관계형 데이터베이스 시스템은 인덱스를 구현하기 위해 앞서 설명한 이진트리를 개선한 "B-트리" 또는 "B-트리의 변형(B+트리 등)"을 사용한다.
• 이진 탐색 트리는 검색에 O(log n)의 성능을 제공하지만, 데이터가 순차적으로 입력되면 한쪽으로 치우쳐지는 문제(Worst Case O(n))가 발생할 수 있다.
  • 이 문제를 해결하기 위해 밸런스 트리(Balanced Tree) 개념이 도입되었고, B-트리는 이러한 밸런스 트리의 한 종류이다.
• 하지만 B-트리가 특별히 중요한 이유는 단순히 균형을 유지하는 것을 넘어, 데이터베이스처럼 대용량 데이터를 다루는 환경에 최적화되어 있기 때문이다.
  • 데이터베이스는 데이터를 메모리가 아닌 디스크에 저장한다.
  • 디스크에서 데이터를 읽는 작업(Disk I/O)은 메모리에서 읽는 것보다 훨씬 느리다. 따라서 디스크 I/O 횟수를 줄이는 것이 성능에 결정적인 영향을 미친다.
  • 이진 탐색 트리는 한 노드가 하나의 데이터만 가지고 있어, 데이터를 검색할 때 여러 노드를 방문해야 한다면 그만큼 디스크에서 많은 블록을 읽어야 한다.
  • 반면 B-트리는 하나의 노드가 여러 개의 자식 노드를 가질 수 있고, 더 많은 데이터를 저장할 수 있도록 설계되었다.
  • 이는 디스크에서 한 번 데이터를 읽을 때 더 많은 정보를 가져올 수 있게 하여 디스크 I/O 횟수를 획기적으로 줄여준다.
    • 덕분에 B-트리는 디스크 I/O를 최소화하면서 대용량 데이터에서 효율적인 검색 성능을 제공한다.