BJ.54-3 B tree가 왜 DB 인덱스(index)로 사용되는지를 설명합니다

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

B-tree 계열이 데이터베이스 인덱스로 사용되는 주된 이유는 세컨더리 스토리지의 접근 횟수를 최소화하여 조회 성능을 극대화하기 위함입니다.

B-tree는 각 노드가 여러 개의 자녀 노드와 데이터를 가질 수 있어 트리의 높이를 낮추고, 블록 단위로 데이터를 읽는 세컨더리 스토리지의 특성을 효율적으로 활용하여 저장 공간 활용도를 높입니다.

B-tree는 이퀄리티 조회뿐만 아니라 범위 기반 검색과 정렬에도 강점을 보여, 해시 인덱스가 가진 제한적인 기능의 단점을 보완합니다.

B-tree 계열은 B-tree를 확장하거나 변형한 B+tree, B*tree 등을 모두 포함합니다. 이러한 B-tree 계열은 데이터를 조회, 삽입, 삭제하는 경우에 대해 평균 및 최악의 시간 복잡도가 모두 **O(logN)**입니다. 여기서 N은 B-tree에 저장된 데이터의 개수를 의미하며, 데이터의 크기가 증가하더라도 로그 함수 형태로 성능을 유지합니다.

반면, 이진 탐색 트리는 자녀 노드를 최대 두 개만 가질 수 있으며, 각 노드에는 하나의 키만 저장됩니다. 이진 탐색 트리가 한쪽으로 기울어질 경우 시간 복잡도가 O(N)까지 나빠질 수 있어, 이를 보완하기 위해 **스스로 균형을 잡는 AVL 트리와 레드 블랙 트리**가 등장했습니다. 이 두 트리는 조회, 삽입, 삭제에 대해 평균 및 최악의 경우 모두 O(logN)의 시간 복잡도를 가집니다.

결과적으로 B-tree 계열과 AVL/레드 블랙 트리 모두 동일하게 O(logN)의 시간 복잡도를 가지게 됩니다. 그렇다면 **왜 데이터베이스(DB) 인덱스로는 B-tree 계열이 주로 사용되는지**에 대한 의문이 생길 수 있습니다.

컴퓨터 시스템 구조와 세컨더리 스토리지의 특징

컴퓨터 시스템은 크게 CPU, 메인 메모리(RAM), 그리고 세컨더리 스토리지로 구성됩니다. CPU는 프로그램 코드가 실행되는 곳이며, 메인 메모리는 **실행 중인 프로그램의 코드와 데이터가 임시로 상주하는 휘발성 메모리**입니다. 반면 세컨더리 스토리지는 프로그램과 데이터가 **영구적으로 저장되는 비휘발성 메모리**이며, DB 데이터도 여기에 저장됩니다.

세컨더리 스토리지의 주요 특징은 다음과 같습니다. 첫째, **데이터 처리 속도가 컴퓨터 시스템 구성 요소 중 가장 느립니다.** RAM이 초당 40~50GB를 처리하는 반면, SSD는 3~5GB, HDD는 0.2~0.3GB에 불과합니다. HDD는 물리적 장치의 움직임 때문에 SSD보다 더 느립니다.

둘째, **데이터 저장 용량이 가장 큽니다.** 메인 메모리에 비해 세컨더리 스토리지의 용량이 훨씬 큰 것을 쉽게 확인할 수 있습니다. 셋째, **데이터를 읽거나 쓸 때 블록 단위로 처리합니다.** 여기서 블록은 파일 시스템이 데이터를 읽고 쓰는 논리적 단위로, 4KB, 8KB, 1MB 등이 있습니다. 특정 데이터를 읽어올 때 해당 데이터를 포함하는 블록 전체를 메인 메모리로 가져오게 됩니다. 이는 연관된 데이터를 한 번에 가져와 효율성을 높이기 위함이지만, 때로는 필요 없는 데이터까지 읽어올 수 있다는 단점도 있습니다.

DB 인덱스로 B-tree가 사용되는 이유: AVL 트리와의 성능 비교

데이터베이스는 영구성과 대용량 저장의 필요성 때문에 세컨더리 스토리지에 저장됩니다. DB 시스템은 핵심 데이터를 메인 메모리에, 나머지는 세컨더리 스토리지에 저장하고, 요청 발생 시 필요 데이터를 블록 단위로 메인 메모리로 가져와 처리합니다. 이때, **DB에서 데이터를 조회할 때 세컨더리 스토리지 접근 횟수를 최소화하는 것이 성능상 매우 중요합니다.**

동일한 조건(루트 노드만 메인 메모리에 있고, 나머지 노드와 실제 데이터는 세컨더리 스토리지에 저장)에서 AVL 트리 기반 인덱스와 B-tree(5차 B-tree 예시) 기반 인덱스의 데이터 조회 성능을 비교했습니다.

AVL 트리 기반 인덱스로 특정 값(예: B=5)을 조회할 경우, 루트 노드에서 리프 노드까지 탐색하는 과정에서 **총 4번의 세컨더리 스토리지 접근**이 발생합니다. 각 노드가 하나의 데이터만 가지고 자녀 노드가 최대 두 개뿐이므로, 데이터를 찾기 위해 여러 단계를 거쳐야 하기 때문입니다.

반면, 5차 B-tree 기반 인덱스로 동일한 값을 조회할 경우, **총 2번의 세컨더리 스토리지 접근**만으로 데이터를 찾을 수 있었습니다. 이는 B-tree가 각 노드에 더 많은 키를 저장하고 더 많은 자녀 노드를 가질 수 있기 때문에, 트리의 높이가 낮아져 루트 노드에서 리프 노드까지의 거리가 짧아지기 때문입니다.

이러한 비교를 통해 B-tree가 AVL 트리에 비해 세컨더리 스토리지 접근 횟수를 현저히 줄일 수 있어 **성능적인 측면에서 훨씬 뛰어나다**는 것을 알 수 있습니다. 세컨더리 스토리지는 데이터 처리 속도가 가장 느리기 때문에, 접근 횟수를 줄이는 것이 매우 중요합니다.

또한, B-tree는 한 노드에 더 많은 데이터를 저장할 수 있으므로, 세컨더리 스토리지에서 블록 단위로 데이터를 읽어올 때 **블록 저장 공간 활용도가 AVL 트리에 비해 훨씬 좋습니다.** 필요한 데이터들을 한 블록에 뭉쳐서 들고 있기 때문에 비효율적으로 불필요한 데이터를 읽어올 가능성이 줄어듭니다.

B-tree의 강력함과 인덱스 적합성

101차 B-tree를 예로 들어 그 강력함을 살펴보겠습니다. 101차 B-tree는 하나의 노드가 최대 101개의 자녀 노드를 가질 수 있으며, 최대 100개의 키를 가집니다. 최선 케이스(각 노드가 최대 데이터를 저장)에서 레벨 3 높이의 101차 B-tree는 **약 1억 개의 데이터를 저장**할 수 있습니다.

최악 케이스(각 노드가 최소 데이터를 저장)에서도 루트 노드 외 다른 노드는 최소 50개의 키와 51개의 자녀 노드를 가지며, 레벨 3 높이의 트리에서 **약 26만 개의 데이터를 저장**할 수 있습니다. 평균적인 경우에는 수백만 또는 수천만 개의 데이터를 저장할 수 있을 것으로 추정됩니다.

이처럼 B-tree는 낮은 트리 높이(단 4개의 레벨)로도 수백만, 수천만 개의 대용량 데이터를 저장할 수 있으며, **루트 노드에서 리프 노드까지의 이동 횟수가 적어 세컨더리 스토리지 접근 횟수를 최소화**할 수 있습니다. 이는 성능 면에서 엄청난 이점을 제공하며, 대량의 데이터를 저장해야 하는 데이터베이스의 인덱스로 매우 적합한 자료 구조임을 보여줍니다.

스스로 균형을 잡는 이진 탐색 트리를 블록 안에 최대한 담아 B-tree와 비슷한 성능을 낼 수 있지 않겠냐는 질문에 대해, 이는 사실상 B-tree가 동작하는 방식과 유사하며, 굳이 AVL 트리를 블록에 압축 저장하는 복잡한 구현을 할 바에는 **B-tree를 사용하는 것이 더 효율적**입니다.

해시 인덱스는 이퀄리티(동등) 조회에서는 성능 이점을 가질 수 있지만, **범위 기반 검색이나 정렬에는 사용할 수 없다는 단점**이 있습니다. 따라서 앞으로도 이퀄리티 조회만 할 것이 확실한 경우가 아니라면, 일반적으로 범위 검색과 정렬이 필요한 상황이 많기 때문에 B-tree 기반 인덱스가 더 널리 사용됩니다.

B-tree 계열과 AVL 트리, 레드 블랙 트리가 모두 O(logN)의 시간 복잡도를 가짐에도 불구하고, B-tree 계열이 DB 인덱스로 더 선호되는 근본적인 이유가 무엇인가요?

세컨더리 스토리지의 주요 특징(느린 처리 속도, 큰 저장 용량, 블록 단위 입출력)이 B-tree가 DB 인덱스로 적합한 이유와 어떻게 연결되는지 설명해주세요.

AVL 트리 기반 인덱스와 B-tree 기반 인덱스의 데이터 조회 과정을 비교했을 때, B-tree가 세컨더리 스토리지 접근 횟수를 줄일 수 있는 구체적인 원리는 무엇인가요?

101차 B-tree의 베스트 케이스와 워스트 케이스 분석을 통해 B-tree가 단지 몇 개의 레벨만으로도 방대한 양의 데이터를 효율적으로 저장하고 접근할 수 있음을 보여주는 이유는 무엇인가요?

AVL 트리도 블록 공간을 효율적으로 사용하게 만들거나 해시 인덱스를 사용하는 방안이 제시되었는데, 그럼에도 불구하고 B-tree가 일반적으로 더 많이 사용되는 결정적인 요인들은 무엇인가요?

B-트리 계열의 시간 복잡도 및 특징 소개

B-트리 시간 복잡도, 세컨더리 스토리지 특징, TV 인덱스 사용 이유 설명

B-트리 계열(B+, B* 트리 등)의 시간 복잡도 분석 필요성 언급

조회, 삽입, 삭제 시 B-트리 계열의 시간 복잡도(평균 및 최악의 경우) 분석

이진 트리 계열 시간 복잡도는 O(log n)임을 설명

바이너리 서치 트리의 일반화 및 자녀 노드 제한(최대 2개) 설명

균형 잡는 바이너리 서치 트리와 B-트리 비교

균형 잡는 바이너리 서치 트리(AVL 트리, 레드 블랙 트리) 소개 및 시간 복잡도(O(log n)) 설명

B-트리와 균형 잡는 바이너리 서치 트리의 시간 복잡도가 동일한데 TV 인덱스로 B-트리가 사용되는 이유에 대한 질문 제기

컴퓨터 시스템 구조 및 세컨더리 스토리지 특징 분석

CPU, 메인 메모리(RAM), 세컨더리 스토리지의 역할과 특징 비교

세컨더리 스토리지의 영구 저장 기능과 메인 메모리와의 차이점(휘발성 vs. 비휘발성) 설명

세컨더리 스토리지의 임시 저장 기능(스와핑) 설명

세컨더리 스토리지의 데이터 처리 속도(RAM, SSD, HDD 비교) 및 저장 용량 특징 설명

세컨더리 스토리지의 블록 단위 데이터 입출력 방식과 효율성 설명

데이터베이스 시스템 동작 방식과 성능 최적화

데이터베이스는 세컨더리 스토리지에 저장되며, 중요 데이터의 영구 저장 필요성 강조

데이터베이스 시스템의 메인 메모리와 세컨더리 스토리지 활용 방식 설명

데이터베이스 성능 최적화를 위한 세컨더리 스토리지 접근 최소화 전략 제시

B+ 트리 인덱스 사용 이유: AVL 트리와의 비교 분석

테이블 데이터 조회 시 인덱스(AVL 트리, B+ 트리) 생성 및 비교를 통한 B+ 트리의 효율성 분석

AVL 트리 기반 인덱스 생성 및 데이터 조회 과정(세컨더리 스토리지 접근 횟수 확인)

B+ 트리 기반 인덱스 생성 및 데이터 조회 과정(세컨더리 스토리지 접근 횟수 확인)

AVL 트리와 B+ 트리의 세컨더리 스토리지 접근 횟수 비교 및 B+ 트리의 성능 우위 분석

B+ 트리의 자녀 노드 수(3~5개)와 AVL 트리(2개) 비교를 통한 탐색 범위 감소 효과 설명

B+ 트리의 노드당 데이터 수(2~4개)와 AVL 트리(1개) 비교를 통한 블록 단위 저장 공간 활용도 비교

100차 B+ 트리의 성능 분석: 베스트 케이스와 워스트 케이스 비교

100차 B+ 트리의 파라미터(최대/최소 자녀 노드 수, 키 수) 설명

100차 B+ 트리의 베스트 케이스(각 노드가 최대 데이터 저장) 시 데이터 저장 용량 계산

100차 B+ 트리의 워스트 케이스(각 노드가 최소 데이터 저장) 시 데이터 저장 용량 계산

100차 B+ 트리의 평균 케이스(베스트와 워스트 케이스 사이) 시 데이터 저장 용량 추정

데이터베이스 인덱스로 B-트리 계열을 사용하는 이유 요약

AVL 트리의 블록 공간 활용 개선 가능성 및 B-트리 사용의 효율성 비교

해시 인덱스의 장단점 비교 및 B-트리 기반 인덱스 사용의 일반성 설명

BJ.54-3 B tree가 왜 DB 인덱스(index)로 사용되는지를 설명합니다

BJ.54-3 B tree가 왜 DB 인덱스(index)로 사용되는지를 설명합니다

스크립트