[DB] 인덱스로 왜 B tree가 사용될까?

B tree란?

B tree란, 이진 탐색 트리를 일반화한 트리이다.

• 이진 탐색 트리(Binary Search Tree)란 아래와 같은 특징을 가진 이진 트리를 말한다.

  

  • 자신의 오른쪽 노드는 자신보다 큰 값을 갖고, 자신의 왼쪽 노드는 자신보다 작은 값을 갖고 있다.
  • 자식 노드를 최대 2개까지 가질 수 있다.

B tree는 아래와 같은 특징이 있다.

• 노드에 key를 여러개 저장할 수 있다.
• 노드의 key들은 오름차순으로 정렬되어 저장된다.
• 정렬된 순서에 따라 자녀 노드들의 key값의 범위가 결정된다.
• 자녀 노드의 최대 개수를 맘대로 결정해서 쓸 수 있다.
• 균형이 잡힌 balanced tree 이기 때문에 최악의 경우나 평균이나 시간 복잡도가 O(logN)이 된다.
  • 반면에, 아래와 같이 균형이 잡히지 않은 이진 탐색 트리의 경우는 최악의 경우에는 시간 복잡도가 O(N)이 나올 수 있다. 최악의 경우의 tree 알고리즘
    

B-Tree의 주요 파라미터

파라미터	설명	비고
M	각 노드의 최대 자녀 노드 수
M-1	각 노드의 최대 key 수
M/2 (올림)	각 노드의 최소 자녀 노드 수	root 노드와 leaf 노드는 제외
M/2-1 (올림)	각 노드의 최소 key 수	root 노드는 제외

각 노드의 최대 자녀 노드 수가 M이면 해당 B-Tree는 M차 B-Tree 라고 한다.

B tree는 각 노드의 최대 자녀 노드수를 파라미터로 갖기 때문에, 자녀 노드의 최대 개수를 맘대로 결정해서 쓸 수 있다. 는 특징이 있다.

왜 DB 인덱스로 B tree가 사용되는가?

시간 복잡도가 뛰어나서?

• B tree 계열(B+ tree, B* tree)은 avg case, worst case 모두 O(logN)의 시간 복잡도를 가진다.
• 이진 탐색 트리 중에 모든 leaf 노드들은 같은 레벨에 두는 self-balancing BST계열(AVL tree, Red-Black tree)의 경우도 avg case, worst case 모두 O(logN)의 시간 복잡도를 가진다.

→ 시간 복잡도 때문이 아니다.

DB의 관점으로 보는 보조 기억 장치

• DB의 데이터는 컴퓨터의 기억장치로 보면 보조 기억 장치(SSD or HDD)에 저장된다.
• 보조 기억 장치는 속도는 느리지만, 용량이 크다.
• 그리고, block 단위로 데이터를 읽고 쓴다.
  • block이란, file system이 데이터를 읽고 쓰는 논리적인 단위를 말한다.
  • 만약, 데이터 하나를 읽어오고 싶다면, 해당 데이터가 들어가 있는 block 전체를 메인 메모리로 가져온다. → 불필요한 데이터까지 읽어올 수 있다.
• 결국 위의 내용으로 아래 두 가지 내용을 알 수 있다.
  1. DB에서 데이터를 조회할 때 보조 기억 장치에 최대한 적게 접근하는 것이 성능 면에서 좋다.
  2. block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있다.

이제, 아래의 가정과 함께 B tree 기반 index와 AVL tree기반 index를 비교해보자.

1. root 노드를 제외한 값들은 보조 기억 장치에 저장되어 있다.
2. 각 노드의 데이터는 다른 block에 저장되어 있다. (같은 노드의 데이터는 같은 block에 저장)
3. DB의 실제 데이터는 보조 기억 장치에 저장되어 있다.

• AVL tree 기반 index 우선, root 노드를 제외한 값들은 보조 기억 장치에 저장되어 있으므로 각 노드의 값을 불러올 때 마다 보조 기억 장치에 접근한다. 그리고, 인덱스에 해당하는 DB 데이터도 보조 기억 장치에 저장되어 있으므로 최종적으로 일치하는 key를 찾았으면, key에 해당하는 데이터를 불러오기 위해 보조 기억 장치에 접근한다. 즉, 위 그림에서 5라는 값을 찾기 위해서는 3, 4, 5, 인덱스에 해당하는 DB 데이터 를 가져오기 위해 보조 기억 장치에 총 4번 접근한다. 또한, 각 노드를 보조 기억 장치에서 가져올 때 block 단위로 가져오므로 필요없는 데이터도 함께 가져온다.
  
• B tree 기반 index (5차) 위 그림에서 5라는 값을 찾기 위해서는 5|6|7, 인덱스에 해당하는 DB 데이터 를 가져오기 위해 보조 기억 장치에 총 2번 접근한다. 각 노드를 보조 기억 장치에서 가져올 때 block 단위로 가져오고, 같은 노드의 데이터는 하나의 block에 저장되어 있으므로 5|6|7 을 한번의 보조 기억 장치 접근으로 가져올 수 있다.
  

이제, 두 자료구조 기반의 index를 비교해보면 이렇게 된다.

• 보조 기억 장치 접근 횟수: B tree < AVL tree
• block 단위에 대한 저장 공간 활용도: B tree > AVL tree

만약, 데이터의 수가 매우 많아진 상태에서 다시 두 index를 비교하게 되면, 보조 기억 장치 접근 횟수와 block 단위에 대한 저장 공간 활용도가 기하급수적으로 차이나게 된다.

예를 들어 101차 B tree의 경우는 1억개의 데이터가 저장되어 있을 때 단 4개의 level로 가장 멀리있는 데이터를 접근할 수 있다.

그렇기 때문에 DB index로 B tree를 가장 많이 사용한다.

참고: 유튜브 "쉬운코드"