[Database] B tree가 데이터베이스 인덱스로 사용되는 이유

왜 데이터베이스 인덱싱에 B트리 계열이 선호되는가?

데이터베이스의 인덱싱에서 B트리 계열이 많이 사용되는 이유를 이해하기 위해서는, 먼저 B트리의 성능 특성과 기본 구조에 대한 이해가 필요합니다. 

B트리는 검색, 삽입, 삭제 연산에 대해 평균적으로나 최악의 경우에도 O(logN)의 시간 복잡도를 제공합니다. 이는 B트리가 이진 탐색 트리(Binary Search Tree, BST)를 일반화한 형태로, BST의 한계점을 극복하고자 설계된 자료구조임을 의미합니다.

BST는 각 노드가 하나의 키를 가지며 최대 두 개의 자녀 노드를 가질 수 있습니다. 하지만, BST는 최악의 경우 선형 리스트와 같은 성능(O(N))을 보일 수 있어, 이를 해결하기 위해 AVL 트리나 레드-블랙 트리와 같은 개선된 자료구조가 개발되었습니다. 이러한 트리 구조들도 평균적으로나 최악의 경우에도 O(logN)의 시간 복잡도를 유지합니다.

그럼에도 불구하고, 데이터베이스 인덱싱에 B트리 계열이 선호되는 까닭은 무엇일까요? 

 

이 질문에 대한 답을 찾기 위해서는 데이터베이스가 운영되는 컴퓨터 시스템의 특성을 고려해야 합니다.

 

 

CPU는 컴퓨터의 두뇌로, 프로그램 코드의 실제 실행을 담당합니다. 한편, 메인 메모리(RAM)는 실행 중인 프로그램의 코드와 해당 코드 실행에 필요한 데이터, 그리고 실행 결과로 생성된 데이터를 일시적으로 저장하는 휘발성 저장소입니다. 이러한 메커니즘은 프로그램 실행의 효율성과 속도를 극대화합니다.

 

세컨더리 스토리지는 프로그램과 데이터를 영구적으로 저장하는 공간으로, 메인 메모리에 비해 상대적으로 느린 접근 속도를 가지지만, 훨씬 큰 저장 용량을 제공합니다. 특히, 실행 중인 프로그램이 메인 메모리에 모두 담을 수 없을 정도로 많은 데이터를 다룰 때, 세컨더리 스토리지에 일부 데이터를 저장하고 필요에 따라 스와핑(Swapping)을 통해 해당 데이터를 메인 메모리로 불러오는 작업을 수행합니다.

 

세컨더리 스토리지의 특징

• 저장 용량:
  • 대용량의 데이터를 저장할 수 있는 가장 큰 장점을 가집니다.
• 데이터 처리 속도:
  • 메인 메모리에 비해 접근 속도가 느리며, 이는 시스템의 전체적인 성능에 영향을 줄 수 있습니다.
• 데이터 관리 방식: 
  • 데이터는 블록 단위로 관리되며, 이는 파일 시스템이 데이터를 읽고 쓰는 기본 단위입니다. 블록 크기는 일반적으로 4KB, 8KB, 16KB와 같이 2의 거듭제곱으로 설정됩니다.

메인 메모리와 Secondary storage의 속도 차이

 

데이터베이스 시스템에서 성능을 최적화하기 위해서는 세컨더리 스토리지에 대한 접근을 최소화하는 것이 중요합니다. 데이터 조회 시, 세컨더리 스토리지에 빈번하게 접근하는 것은 시스템의 성능을 저하시킬 수 있으므로, 필요한 데이터를 효율적으로 접근하고 관리하는 전략이 필요합니다.

이러한 전략에는 데이터를 블록 단위로 효율적으로 읽고 쓰는 것이 포함됩니다. 연관된 데이터를 같은 블록에 저장함으로써 데이터 접근 시간을 단축시키고, 세컨더리 스토리지의 효율적 사용을 극대화할 수 있습니다.

 

 

예제 시나리오를 위한 테이블이 있습니다. 이 테이블에서 b 컬럼에 해당되는 데이터를 조회하는 쿼리를 사용합니다.

 

성능 향상을 위한 인덱스를 생성할건데, AVL tree 인덱스, B tree 인덱스 두 개를 생성해서 둘의 세컨더리 스토리지 접근 횟수를 비교해보겠습니다.

 

전제조건

초기에는 루트노드를 제외한 모든 노드는 세컨더리 스토리지에 저장되어있습니다.

테이블의 모든 데이터 또한 메인 메모리에 저장되어있지 않고, 세컨더리 스토리지에 저장되어있습니다.

WHERE 조건으로, b가 5인 레코드를 조회합니다.

 

먼저 AVL tree 인덱스를 사용해 데이터를 조회해볼건데, 해당 인덱스는 다음과 같은 구조를 가지고있습니다.

 

 

• 검색 시작:
  • 루트 노드의 값이 '6'입니다. 찾고자 하는 키 값 '5'는 '6'보다 작으므로, 트리의 왼쪽 자식 노드로 이동합니다.
• 왼쪽 자식 노드 접근:
  • 이제 '3'이라는 값을 가진 노드에 도착했습니다. '5'는 '3'보다 크므로, 이 노드의 오른쪽 자식 노드로 이동합니다.
• 오른쪽 자식 노드 접근:
  • 다음으로 '4'라는 값을 가진 노드에 도착했습니다. '5'는 '4'보다 크므로, 다시 오른쪽으로 이동합니다.
• 값 발견:
  •  '5'라는 값을 가진 노드를 찾았습니다. 이로써 인덱스를 통한 조회 과정은 끝났습니다.
• 데이터베이스 힙 접근:
  • 인덱스를 통해 찾은 키 값 '5'에 해당하는 실제 데이터를 데이터베이스의 힙에서 가져와야 합니다. 

이 과정에서 총 4번의 secondary storage 접근이 발생했습니다

 

 

이번에는 5차 B 트리 인덱스를 사용하여 데이터를 조회하는 과정을 설명하겠습니다.

 

• 검색 시작:
  • 루트 노드의 값이 '4', '8'입니다. 키 값 '5'는 '4'보다 크고 '8'보다 작기 때문에, 중간 노드로 접근합니다. 
• 중간 자식 노드 접근:
  • 중간 노드에서 5를 찾으면 인덱스 조회는 완료됩니다. 이제 데이터베이스 힙에서 실제 데이터를 가져와야 합니다.

이 과정에서 총 2번의 세컨더리 스토리지 접근이 이루어졌습니다. 이는 AVL 트리를 사용한 경우와 비교하여 매우 효율적입니다.

B 트리의 차수에 따라 다르겠지만, AVL 트리는 탐색 범위가 항상 1/2로 줄어들기 때문에 B 트리에 비해 선택지가 적고 접근 거리가 길어질 수밖에 없습니다. 또한, AVL 트리는 각 노드가 하나의 키만 가질 수 있지만, B 트리는 M-1개의 키를 가질 수 있습니다.

따라서, 세컨더리 스토리지 에서 데이터를 읽어올 때 B 트리는 블록 단위로 데이터를 읽어오므로 저장 공간 활용도가 훨씬 높습니다. 이로 인해 B 트리는 대규모 데이터베이스에서 더욱 효율적인 인덱싱 방법이 될 수 있습니다.