[DBMS] Index & B+ Tree

본 내용은 한양대학교 차제혁 교수님의 DBMS 강의자료를 바탕으로 작성되었습니다. 
추가로 B+ Tree 자료구조에 관한 내용은 https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree 을 참고했습니다. 

Two ways to access

앞서 보았듯 데이터에 접근하기 위한 방법은 크게 2가지가 있었는데 

1. 페이지의 시작부분부터 모두 스캔하는 방법

2. 레코드 ID(페이지 아이디, 슬롯 아이디) 를 이용하여 접근하는 방법

이 존재했다. 

 

하지만 값을 기반으로 기준으로  record를 찾을 수 있다면 좋지 않을까..?

이를 위해 Index가 필요하다.

 

Index

An index is data structure that enables fast lookup of data entries by search key

• Lookup: may support many different operations – Equality, 1-d range, 2-d region, …
• Search Key: any subset of columns in the relation – Do not need to be unique—e.g. (firstname) or (firstname, lastname)
• Data Entries: items stored in the index
• Many Types: B+-Tree, Hash, R-Tree, GiST, .

Index란 데이터를 키를 통해서 매우 빠르게 찾고 변경할 수 있는 자료구조이다.

테이블의 특정 column을 key로 잡고 정렬하고 실제 레코드의 참조값을 저장한다.  (키, 레코드 아이디) 키를 통해서 레코드 아이디를 확인할 수 있고 레코드 아이디에는 (페이지 아이디, 슬롯 아이디)가 저장되어 있으므로 슬롯 아이디를 통해서 데이터를 찾을 수 있다. 

아래와 같이 간단하게 Sorted (key, pageid) 부터 시작해보자. Binary search가 sorted 되어있음으로 가능할 것이다. 

 

Page를 연결하기 위해 포인터가 필수적인가? 아니다. 이미 페이지들은 논리적인 순서대로 디스크에 정렬되어 저장되어있기 때문이다. 아래의 그림과 같이 High Fan-Out Search Tree를 만드어보자(자식 노드를 가질 수 있는 Search Tree를 지칭, Binary tree와 달리 더 많은 자식노드 허용)

Node […, (KL, PL), (KR, PR), ... ]  All tuples in range KL <= K < KR are in tree PL

위의 그림은 키에 의해서 정렬된 (키, 페이지 id)의 인덱스 구조이며, 실제 데이터보다 더 적은 양의 데이터로 페이지를 가리키게 된다. 키보다 같거나 작은 값은 왼쪽에 같거나 큰값은 오른쪽에 저장된다. 데이터 검색 시 루트 인덱스부터 시작해서 아래로 내려간다. 

이 Tree의 Search complexity는 O(logF(#pages))이다. 

 

ISAM Indexed Sequential Access Method

ISAM IBM의 indexting 기술로 인덱스 순차 접근 방법의 줄임말이다. 즉, 데이터를 정렬된 순서로 저장하고 인데스를 활용하여 CRUD를 효율적으로 할 수 있는 파일 관리 방법을 말한다. 이는 데이터와 인덱스를 별도로 관리하며 읽기 성능 최적화에 중점을 둔다. 

ISAM은 아래 그림과 같이 데이터파일과 인덱스 파일을 나누어 관리하며 정적이다. 

 

(1) 데이터 파일: 데이터를 정렬된 순서로 저장하는 파일로 데이터의 물리적 순서가 고정되어 삽입이나 삭제 후에도 재정렬되지 않음.
(2) 인덱스 파일: 데이터 파일에 대한 포인터를 저장.
계층 구조로 관리되며, 빠른 검색을 위해 상위 인덱스(Primary Index)와 하위 인덱스(Secondary Index)로 나누어진다. 

루트 인덱스는 데이터를 분할하며 하위 인덱스는 각 범위 내에서 데이터 블록을 가리킨다. 

 

추가적으로 위의 그림과 그 이전 그림을 비교하면 1, 7이 없어져있는데(각 index에서 가장 왼쪽에 있는 값 제거) 이는 인덱스에 있는 값보다 작으면 왼쪽에 있다는 것을 알 수 있기 때문이다.

 

만일 데이터를 더 추가한다고 가정해보자. 만일 11과 12를 추가한다면 11까지는 괜찮지만 12는 overflow가 나게 됨으로 새로운 페이지를 생성후에 바로 직전 페이지를 통해 이를 가리키게 한다. 물론 이럴 경우 데이터 추가가 많이 일어날 수록 linked list 형태가 됨으로 접근에 비효율적이라는 문제가 있다. 

 

이러한 ISAM은 1960년대에 IBM에서 나온 개념이고 B+ tree가 대부분 더 좋지만 기본적인 구조로 알아둘만한다(동적으로 변환!)

 

B+ Tree in DBMS

B+ Tree는 동적인 형태의 데이터 구조로 효율적인 삽입과 삭제 연산을 지원한다. 이는 ISAM은 LEAF 노드만을 증가시키는 구조인데 비해 B+ Tree는 루트 및 중간 노드를 증가시키는 방법을 선택했기 때문이다. 

이를 Dynamic Tree index라고 한다. 

B+Tree 자료구조에 관해 간단히 정리하면 트리구조에서 발전하여

1.모든 리프 노드들이 같은 레벨을 갖춘다 2. 리프 노드가 연결리스트 관계를 가진다 라는 특징을 지니고 있다. 

 

 

B+ tree의 경우 data page가 logical order로 저장되지 않을 수도 있다(locigal order != pshyical data order)

B+ tree의 구조를 정리하면 아래와 같다. 

• 루트 노드(Root Node): 트리의 시작점이며, 최상위 노드. 데이터를 분할하는 키를 포함.
• 내부 노드(Internal Nodes): 검색 경로를 제공하며, 자식 노드를 가리키는 포인터와 분할 키 값을 저장.
• 리프 노드(Leaf Nodes): 실제 데이터를 포함하고, 리프 노드는 서로 Linked list로 연결되어 있어 순차적 접근이 가능.
• 팬아웃(Fan-out): 한 노드가 가질 수 있는 최대 자식 노드 수.

 

 

B+ Tree의 Scaling은 아래와 같이 계산가능하다. 

 

우선 Root node에서 분할점의 개수를 d라고 하면 Fanout은 2d+1로 계산된다. 

그럼으로 Height 1에서 Fanout = 2d + 1=  5, page당 record가 4개씩이라고 가정하면 20 record가 존재한다.

Height 2에서는 각각의 Fanout 당 다시 동일한 분할점이 존재한다고 하면, 5^2 * 5 = 100개 3층에서는 5의 3승 곱하기 4로 점점 기하급수적으로 늘어나는 scaling 특징을 지닌다. 

+) Scale for hieght = (2d+1)^H * R 

아래에서 다루는 내용들은 대다수 B+ Tree의 자료구조 내용과 거의 동일하다는 것을 확인하자

Searching B+ Tree

데이터를 찾아가는 과정은 우선 루트 노드에서 시작해서 찾으려고 하는 키가 현재 분할점보다 큰지 작은지 비교하면서 검색한다. 최종적으로 리프노드에 도달한다면 해당 레코드 id로 원하는 데이터에 접근가능하다.

아래는 key 27을 찾는 예시이다. 

 

Inserting record in B+ Tree

데이터 삽입의 경우 삽입하려는 노드가 Full인 상태에는 분리를 해야기에 이를 고려해야한다. 아래의 두 예시를 통해 살펴보자. 

- Full하지 않은 경우: Insert 25

위와 같은 B+ tree에 25를 insert하려고 한다고 해보자. 그러면 올바른 위치에 Lear node를 찾고 입력한 다음 해당 leaf page를 다시 sorting하는 과정을 거치는 다소 간단한 과정을 거친다.

 

- Full한 경우: Insert 8 

그럼 25를 입력한 이후 8을 insert하는 경우라고 해보자.

동일하게 8을 입력할 leaf를 탐색한다. 그런데 해당 leaf에 보다시피 room이 충분치 않은 상황이다. 그럼으로 Leaf Spliting이 필요한 경우이다. 

Spliting  B+ Tree?

원래 B+ Tree의 분할은 리프노드인 경우와 아닌경우로 나누어지지만, DB에서 데이터 추가는 리프노에서만 일어남으로 리프노드인 경우만 다룬다. 

이 경우 삽입되는 page에 해당하는 중간 key를 부모 key로 올리고 동시에 오른쪽 노드에 중간 key를 포함하여 분할합니다. 또한  연결리스트를 유지하깅 위 왼쪽 자식노드와 오른쪽 자식 노드를 이어줘 연결리스트 형태를 유지한다. 

그림의 case에서는 2, 3, 5, 7, 8로 들어가고 14 16 이어야함으로 

중간부분인 5 key를 기준으로 분할을 진행한다. 

이후 새롭게 추가된 5 key를 위의 노드에 push up, 밀어넣는다. 

 

최종적으로 아래와 같이 변한다. 

Holding Occupancy invariant

Occupancy invariant는 B+ 트리에서 모든 노드(루트 제외)가 최소 절반 이상 데이터(키 or 레코드)를 채운 상태를 유지해야한다는 속성이다. B+ 트리는 삽입과 삭제 작업 후에도 이 속성을 유지하도록 설계되어 있다. 

 

우선 삽입에서의 경우 위에서 보았든 split이 이루어질 때 두 그룹으로 나누어 균등하게 분배하기 때문에 유지될 것이다. 

아래의 그림을 보자, 이때 그림의 d는 최소 데이터 엔트리 수, 즉 각 block의 최대 record 크기의 1/2이다. 

B+-Tree Deletion

특정 data를 삭제할 때도  해당 데이터가 속해있는 leaf를 먼저 찾아야한다. 찾은 이후 케이스는 아래 2가지 경우로 나누어진다. 

찾은 leaf L이 1. 최소 절반보다 많은 개수를 가지고 있을 때는 바로 삭제를 하면된다. 

2. 아닌 경우 위에서 말한  Occupancy invariant를 위해 재분배하는 과정이 필요하다. 

이 경우 sibiling에게(같은 부모를 가지는 형제노드) 데이터를 빌려오거나 merge해야한다. 

 

단, 삭제의 경우 항상 ocuupancy invaraint를 보장하지는 못하며 이는 추가적인 디스크 I/O와ㅓ 성능에 문제를 일으킬 수 있기 때문이다. 따라서, 삭제 시 일부 조건 위반은 용인하고, 반드시 필요할 때만 재균형 작업을 수행합니다(예: 병합 또는 재배치). 

 

다만, 장기적으로 이를 수행하지 않을 경우 

 

• 트리 불균형: 일부 노드가 과도하게 비워지거나, 리프 노드 간 데이터 분포가 고르지 않을 수 있음.
• 효율성 저하: 일부 검색 경로에서 디스크 I/O가 증가할 가능성이 있음.

으로 인한 성능저하가 있을 수 있다. 

 

BULK LOADING B+-TREES

이미 만들어진 테이블에서 B+ Tree 인덱스를 생성하는 경우는 어떻게 할 것인가? 

하나씩 데이터를 집어넣어서 인덱스를 만드는 과정을 효율적이지 않을 것이다. 왜냐하면 데이터를 넣을 때마다, 루트 노드를 통해서 검색을 해야하며, 데이터가 삽입되면서 많은 페이지들이 변경되는 등 노드 분할이 자주 발생하여 비용이 크고 느릴 것이다. 

이런 상황을 해결하기 위해 Bulk loading이 필요하다. 

 

Bulk Loading은 B+-트리에 데이터를 하나씩 삽입하는 대신, 대량의 데이터를 한 번에 트리에 삽입하는 방식으로 데이터를 미리 정렬한 후 삽입하여 삽입 성능을 최적화하는 방법이다. 정렬이 이루어져있다면 루트를 모두 거칠 필요없이 모든 리프노드를 미리 생성한 다음에 중간 노드나, 루트 노드를 업데이트 할 수 있다.

 

과정은 아래와 같다. 

(1)  데이터 정렬
데이터를 키 값을 기준으로 정렬.
B+-트리는 정렬된 데이터에서 가장 효율적으로 구성되므로, 정렬은 필수적인 전처리 과정.

(2) 리프 노드 생성
정렬된 데이터를 바탕으로 **리프 노드(Leaf Nodes)**를 채움.
각 리프 노드는 트리에서 지정된 **노드 크기(최대 엔트리 수)**를 채울 때까지 데이터 추가.
리프 노드 간 링크드 리스트로 연결.

(3) 상위 레벨 노드 구축
리프 노드에서 첫 번째 키(또는 경계 값)를 추출하여 **부모 노드(Internal Nodes)**를 생성.
부모 노드가 가득 차면, 다시 분할하고 상위 노드로 이동.

-> 즉, 공간이 모다를 때마다 부모 노드를 생성 
이 과정을 반복하여 루트 노드까지 구성.

 

이러한 방식은 캐시를 좀 더 효율적으로 사용할 수 있게 해주고, 리프 노드가 디스크 상에 순차적으로 저장이 되므로 매우 효율적이다