[Database] B+Tree 자료구조

 

 

 

데이터베이스에서 특정 값을 검색할 때 해당 컬럼에 인덱스가 없는 경우 전체 테이블을 처음부터 끝까지 탐색하는 Full Table Scan을 수행한다.

 

테이블에 데이터가 많이 저장되어있고 해당 컬럼에 인덱스가 없으면 쿼리 실행 속도가 매우 느리다.

물론 DBMS가 내부적으로테이블을 쪼개서 멀티쓰레딩 및 병렬처리를 수행하겠지만.. 전체 테이블을 탐색하는 작업은 오버헤드가 크다. 

 

효과적인 탐색을 위해 컬럼마다 인덱스를 구축하고 사용한다.

인덱스 구축에 사용되는 내부 자료구조는 B+Tree / 해시 인덱스 / GIN / R-Tree 등 다양한 등 다양하다.

그 중  범용적으로 사용되는 B+Tree에 대해 살펴보자. 

 

 

B-Tree

데이터의 삽입, 삭제, 검색을 효율적으로 수행할 수 있게 설계된 이진 트리의 일종으로 Search Space를 줄여준다. 

 

트리 자료구조의 한 종류로 노드와 그 노드 사이의 부모-자식 관계로 이루어진다.

일단 트리 구조를 유지해야 하니.. INSERT 시 적절한 위치를 찾고 필요 시 분할하는 과정을 거쳐야 해 B-Tree 인덱스가 있을 때는 INSERT 작업 시간이 늘어난다. 

 

노드는 Key-Value로 구성되고, Disk Page를 의미한다. 

 

Key : 데이터를 정렬하고 검색할 때 사용되는 값으로 정렬된 상태를 유지한다. 

Value : 키와 연관된 데이터의 포인터를 의미한다. 데이터 레코드 자체를 저장하지 않고 해당 레코드가 저장된 위치를 가리킨다.

Disk Page : 디스크 상에서 데이터를 읽고 쓰는 기본 단위로, 데이터베이스는 이 페이지 단위로 입출력을 수행한다. 
B-Tree의 노드는 하나의 디스크 페이지에 저장될 수 있도록 설계되고 노드의 물리적 저장 단위로 디스크 페이지를 사용한다. 

 

 

 

 

 

TID는 데이터베이스 내부적으로 저장하는 RowId로 생각하자.

 

B-Tree 인덱스를 생성할 때 선택한 컬럼에 대해 정렬된 상태로 저장되는 자료구조가 만들어지고, 키 값의 정렬 상태 덕분에 O(log n) 시간복잡도로 검색을 수행할 수 있다. 

 

예시에서 Key값이 1인 데이터를 찾는다고 해보자.

탐색에 사용되는 데이터는 Key값 뿐이고, Value는 탐색에서 사용되지 않는다.

 

즉, 노드에 저장되는 Value는 탐색에서 사용되지 않는다.

실제 데이터에 접근할 때는 필요하지만 인덱스 자체에서는 Key값만 필요하니 포인터로 사용되는 Value를 노드에 함께 저장하는건 효율적이지 않다. 

 

대규모 데이터베이스에서 B-Tree 인덱스를 생성할 때 노드에 저장되는 Value 때문에 인덱스의 크기도 커지게 되고, 크기가 커짐에 따라 메모리 사용과 탐색 시간이 증가한다. 

 

 

B+Tree

B-Tree의 단점을 보완하기 위해 도입된 자료구조이다.

 

B-Tree와 유사하지만 Value를 리프 노드에만 저장해 공간을 좀 더 효율적으로 사용하고, 리프 노드끼리는 서로 연결돼있어 목표 Key를 찾은 경우 인접한 Key를 쉽게 찾아갈 수 있다. 

 

 

 

 

B+트리에서 리프 노드에는 Key, Value 외에도 양방향 링크 관련 연결 정보도 저장해 Range Query도 B-Tree에 비해 효율적으로 처리할 수 있다.

 

MySQL, SQL Server, PostgreSQL 등 RDB는 물론, NoSQL 기반인 MongoDB도 B-Tree의 변형인 WiredTiger 스토리지 엔진을 사용한다.

 

대부분의 DBMS가 B+Tree를 사용해서 인덱스 자료구조를 구축하지만 .. 
세부적인 내용은 각 DBMS마다 다르니 데이터베이스를 선택하거나 다룰 때는 각 시스템의 데이터 저장 구조, 트랜잭션 관리 방식, 쿼리 최적화 매커니즘을 고려하자.