B+ 트리 인덱스 기반 탐색에 대해 [B-트리 삽입,탐색,삭제]

https://github.com/IMGyuGo/B_PLUS-TREE

GitHub - IMGyuGo/B_PLUS-TREE: DB B+ 트리 인덱스 기반 탐색 - 팀원 : [김규민, 김원우, 김은재, 김용]

기존 다른 팀원분의 DB SQL Processor를 기반으로 B+ 트리 인덱스 기반 탐색 까지 추가하면서 하루 동안에 Top-Down 방식으로 공부를 진행한 내용에 대한 프로젝트이다.

 

이번 프로젝트 진행 :

• 10시 ~ 11시 (B+ Tree에 대해 학습)
• 11시 ~ 12시 (레포를 나누고, 셋팅을 나눈 뒤 가볍게 B+ 트리의 탐색과 삽입 과정 공유)
• 12시 ~ 오후 2시 (B+ 트리가 무엇인가를 가볍게 나눈뒤, 프로젝트 진행 기획 (무엇을 보여줄 것인가?))
  • 첫번째 : Age를 기반으로 Range 범위 탐색 (왜냐하면 DB 인덱스 탐색을 B+ 트리로 쓰는 이유중 하나)
    • 기존 선형탐색과 B+ 트리를 만든 인덱스 기반 탐색의 속도 비교
  • 두번째 : B+ 트리의 높이에 따른 변화가 있을지에 대한 범위 탐색 결과 비교
    • M :128 (height 3), M : 4 (height 13)
• 오후 2시 ~ 오후 3시 반 (프로젝트의 스텁 코드 생성 + 역할 분담 + 하네스 엔지니어링 'ㅎ' 도입)
• 오후 3시 반 ~ 오후 4시 반 (구현)
• 오후 4시반 ~ 오후 10시 (코드 공부)
• 오후 10시 ~ 새벽 4시 (테스트 케이스 검증 및 오류 수정)
• 새벽 4시 ~ 새벽 6시 반 (발표 준비)

B- 트리란?

정렬된 데이터를 균형 있게 저장해서, 빠르게 탐색/삽입/삭제를 하기 위한 트리 구조

• 하나의 노드에 여러 개의 key 저장
• 모든 리프 노드의 높이가 동일 (균형 트리)
• 탐색: O(log n)
• 자식 수 = key 개수 + 1

“디스크 접근을 최소화하기 위해, 한 노드에 여러 데이터를 담는 균형 탐색 트리”

 

B+ 트리란?

B-트리를 개선해서, 데이터는 리프에만 저장하고 리프를 연결한 구조

• 내부 노드: 탐색용 key만 존재
• 리프 노드: 실제 데이터 저장
• 리프 노드끼리 연결 리스트 형태
• 범위 검색 (range query)에 매우 강함

 “데이터를 리프에만 모아두고, 리프를 연결해 범위 탐색을 빠르게 만든 트리”

B- 트리 탐색, 삽입, 삭제

규칙

차수(M) : 루트 노드가 아닌 한 노드가 가질 수 있는 최대 자식 수

최소차수(t) : 한 노드가 가질 수 있는 최소 자식 수

한 노드에서 가질 수 있는 자식 개수 범위 : ceil(M/2) ~ (M) (M이 3일 경우, 2 ~ 3개) (M이 4일 경우, 2 ~ 4개) ... ⓐ

한 노드에서 가질 수 있는 key 개수범위 : ceil(M/2) - 1 ~ (M-1) (M이 3일 경우, 1 ~ 2개) (M이 4일 경우, 1 ~ 3개) ... ⓑ

데이터 개수(v) = 키 개수(k)
부모노드 키개수(k) 아래 자식노드의 키개수(k1) -> k1 = k + 1 ... ⓒ

 

삽입

삽입과정은 위와 같다. 1부터 9번까지 설명을 하자면,

1을 먼저 루트에 삽입
2를 1옆에 추가
3을 2옆에 추가 (key 개수 위배) -> 분리
4를 3옆에 추가
5를 4옆에 추가 (key 개수 위배) -> 분리
6을 5옆에 추가
7을 6옆에 추가 (key 개수 위배) -> 분리 (자식 노드 개수, key 개수 둘다 위배) -> 분리
8을 7옆에 추가
9를 8옆에 추가 (key 개수 위배) -> 분리

 

탐색

 

삭제

Lmax = 현재 노드의 왼쪽 자식들 중 가장 큰 key

Rmin = 현재 노드의 오른쪽 자식들 중 가장 작은 key

 

🔴 Case1 : 리프 노드에서 삭제

🔴 Case 1-1 : 자식개수범위, key 개수 범위를 위해하지 않는 경우

- 17 삭제

그대로 탐색 후 규칙을 다 잘 적용하므로 문제없이 삭제

 

🔴 Case 1-2 : 옆 노드에서 빌려올 수 있는 경우

- 14 삭제

삭제 후, 규칙이 안 맞는 부분을 맞추기 위해 옆 10번노드를 부모로 13번 노드를 자식으로 옮김

 

🔴 Case 1-3 : 부모노드를 분할할 수 있을 때

- 9 삭제

삭제 후, 규칙이 안맞는 부분을 맞추기 위해 부모노드에서 분할해서 자식노드에게 전달

 

🔴 Case 1-4 : 2,3 둘다 못하는 경우

- 5 삭제

5 삭제 후, 6,7 노드 합체 후 부모를 분할해서 2번노드에 전달 (Case 2-2와 동일)

 

🔵Case 2 : 리프 노드가 아닌 내부 노드에서 삭제

🔵 Case 2-1 : 교환 후 리프 삭제까지 문제없이 끝나는 경우

- 15 삭제

먼저 Lmin 값인 13과 교환해서 삭제 -> 정상적으로 규칙 만족

 

🔵 Case 2-2 : 교환 후 리프에서 삭제하면 언더플로가 발생하는 경우

- 13 삭제

먼저 Lmin, Rmax 둘다 교환해봐도 리프 삭제 연산이 적용이 안됨 -> Case 1-4와 똑같이 합체 후 [2,4] 노드에 전달 후 기존 삽입 과정과 똑같이 분할 진행

 

B+ 트리 탐색, 삽입, 삭제

B- 트리의 탐색, 삽입, 삭제만 알면, B+ 트리를 인터넷에 검색하기만 해도 쉽게 이해가 가능할 것이다.
규칙은 같다
다른 점은 리프에 값을 다 저장하기 때문에
노드 기준 오른쪽에 있는건 같거나 큰것 (리프 노드 기준)
노드 기준 왼쪽에 있는건 작은 것을 의미한다. (리프 노드 기준)
노말 노드 기준으로는 b- 트리와 아예 같다.

 

DB의 인덱스 기반 탐색을 하는데 쓰이는 자료구조가 B+트리인 이유

자료구조	탐색 복잡도	디스크 접근	범위 검색	정렬 유지	특징	DB 성능
배열 (정렬)	O(log n)	❌ (비효율적)	✔ (빠름)	✔	이진 탐색 가능	❌ 삽입/삭제 O(n)
연결 리스트	O(n)	❌	❌	❌	순차 접근만 가능	❌
해시 테이블	O(1) (평균)	❌	❌	❌	키 기반 빠른 조회	❌ 범위 검색 불가
이진 탐색 트리 (BST)	O(log n) (평균)	❌	✔	✔	균형 깨지면 O(n)	❌ 불안정
AVL / Red-Black Tree	O(log n)	❌	✔	✔	균형 유지	⚠ 디스크 비효율
B-트리	O(log n)	✔	✔	✔	노드에 여러 key	✔
B+트리	O(log n)	✔✔	✔✔✔	✔	리프 연결 구조	⭐⭐⭐ (최적)

 

프로젝트를 통해 알게 된 점

- 프로젝트 테스트 결과

한 행 조회
기본 실행 : B+트리를 통해 탐색한 시간
선형 스캔 : 풀스캔을 통해 탐색한 시간

B+ 트리 탐색 시간이 월등히 빠르다.

 

범위 조회
탐색 시간 : 실제 메모리 상에서의 탐색 시간
실제 실행 : 사용자까지 전달된 실제 시간

B+ 트리 탐색 시간이 월등히 빠르다.

범위 조회 (대규모 데이터)
탐색 시간 : 실제 메모리 상에서의 탐색 시간
실제 실행 : 사용자까지 전달된 실제 시간

메모리 상에서의 탐색 시간이 인덱스가 빠르지만
실제 실행시간은 인덱스가 느림
대규모 데이터 조회시 인덱스 기반보다 풀스캔이 훨씬 더 빠른 경우가 존재
메모리 접근 효율성이 떨어져 공간 지역성이 낮은 경우가 반복되어 캐시 힛트가 적어지고,
선형스캔이 유리한 지점이 존재하게 된다.
이 지점을 실제로 SQL 옵티마이저가 자동 계산해서 처리해주는 과정이 존재한다.
계산 완료 후, 그 지점에서 인덱스 탐색이 아닌 풀스캔으로 자동으로 변경해준다고 한다.

이 테스트를 통해 알고 싶던건 높이에 따른 disk i/o의 차이가 얼마나 큰지 알고 싶었는데, B+트리를 디스크 상에서 돌아가게 만들지 않고, 메모리상에서 돌아가게 만들어 둬 인덱스를 생성하고 B+ tree가 만들어지면서 캐시 힛트가 지속적으로 발생하면서 유의미한 결과를 보진 못하고 있다.
탐색시간을 보면 큰 차이가 나는 것도 볼 수 있는데 이건 임의로 높이가 변할때 마다 disk i/o이 발생하는 것처럼 파일 입출력을 실제로 넣어뒀기 때문에 발생하는 결과이다.
유의미한 결과를 얻진 못했기에 10층 정도의 높이가 차이났을 때 얼만큼 차이 나는지를 조사해보았고, 대략 1.2배~ 2.5배 정도의 차이가 난다고 한다.