동호의 블로그


cleanUrl: /B트리의-개념과-특징
floatFirstTOC: right

BST(이진 탐색 트리) 복습 그런데, 자식 노드를 3개로 만들고 싶다면?B트리의 구조적 확장 B트리의 핵심 특징 정리 B트리의 주요 파라미터들 B트리의 삽입 반복 삽입을 통해 완성되는 B트리의 특징 1. 모든 리프 노드가 동일한 레벨에 위치한다.2. 평균 / 최악의 탐색 성능 = O(logN)참고 자료

BST(이진 탐색 트리) 복습

우리는 과거에 이진 탐색 트리(Binary Search Tree, BST)에 대해 배운 적이 있다.

간단히 말하면 BST는 다음과 같은 특징을 갖는다.

모든 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값만 존재하고,

모든 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값만 존재한다.

예를 들어, 어떤 노드의 값이 20이라면 왼쪽 자식에는 20보다 작은 값, 오른쪽 자식에는 20보다 큰 값이 들어나는 구조다.

그리고 이 BST의 중요한 제약이 하나 있다.

바로, 각 노드는 최대 자식 노드를 2개까지만 가질 수 있다는 것이다.

그래서 이름이 ‘이진(Binary)’ 탐색 트리이다.

그런데, 자식 노드를 3개로 만들고 싶다면?

이런 생각이 들 수 있다.

“BST는 자식이 두 개까지만 되는데, 세 개나 네 개는 안 되는 걸까?”

이 의문에서 출발한 자료구조가 바로 B트리이다.

B트리는 BST에서 한 발 더 나아가, 자식 노드를 2개 이상 가질 수 있도록 만든 자료구조이다.

그럼 어떻게 자식 노드를 3개로 만들 수 있을까?

BST에서는 부모 노드의 값을 기준으로 왼쪽/오른쪽으로 값을 나눴다.

이 아이디어를 확장해보면 자식 노드를 세 개 이상 만들 수 있다.

부모 노드에는 두 개의 키 값(K1, K2) 을 저장한다.

그러면 자식 노드를 세 개로 분기할 수 있다.

왼쪽 자식: K1보다 작은 값
가운데 자식: K1보다 크고 K2보다 작은 값
오른쪽 자식: K2보다 큰 값

즉, BST에서의 “좌우로만 나누는 기준”을 “범위 기준으로 분리” 하여 더 많은 자식을 두는 형태로 발전시킨 것이다.

B트리의 구조적 확장

사실 자식 노드를 기준으로 설명했지만, 우리는 트리를 다룰 때 자식 노드 = 서브트리(Subtree) 로도 생각할 수 있다.

그래서 위에서 말한 각각의 자식 노드는 모두 서브트리로 확장될 수 있다.

왼쪽 서브트리: 모든 노드가 K보다 작은 값

가운데 서브트리: 모든 노드가 K1보다 크고 K2보다 작은 값

오른쪽 서브트리: 모든 노드가 K2보다 큰 값

이런 방식으로 전체 트리를 구성하면, 기존의 이진 탐색 트리처럼 탐색 성질을 유지하면서도 자식 수를 유연하게 조절할 수 있는 트리를 만들 수 있다.

B트리의 핵심 특징 정리

지금까지의 설명을 정리해보자.

BST	B트리
자식 노드 최대 2개	자식 노드 2개 이상 가능
노드에 값 하나 저장	노드에 값 여러 개 저장
탐색 기준: 하나의 값	탐색 기준: 여러 값으로 범위 나눔

B트리는 BST의 성질을 확장해서 만든 자료구조로, 한 노드가 여러 개의 값을 가지고, 자식 노드도 여러 개 둘 수 있다는 점이 특징이다.

그래서 B트리는 흔히 “BST의 일반화된 형태” 라고도 불린다.

B트리의 주요 파라미터들

B트리를 정의할 때 가장 중요한 값이 있다.

바로, 한 노드가 최대로 가질 수 있는 자식 노드의 개수이다.

이 값을 보통 m이라고 부른다.

그리고 m차 B트리라고 표현한다.

예를 들어, 3차 B트리는 하나의 노드가 최대 3개의 자식을 가질 수 있는 B트리를 의미한다.

이 m값에 따라 자연스럽게 결정되는 값들이 있다.

	각 노드의 최대 자녀 노드 수
	각 노드의 최대 key 수
	각 노드의 최소 자녀 노드 수 *
	각 노드의 최소 key 수 **

기호: ‘올림’을 의미 * root node, leaf node 제외 ** root node 제외

B트리의 삽입

이번에는 B트리에 데이터를 삽입하는 방식을 실제 예제를 통해 단계별로 정리해보자.

삽입 과정에서 중요한 세 가지 포인트가 있다.

추가는 항상 leaf 노드에 한다.

노드 안 데이터는 오름차순 정렬되어야 한다.

노드가 넘치면 가운데(median) key를 기준으로 좌우 key들은 분할(split)하고 가운데 key는 승격(promote)한다.

3차 B트리 데이터 삽입을 예로 들어보자.

1 추가

트리가 비어 있는 상태에서 시작한다.

노드가 넘치지 않기 때문에 그대로 1을 삽입한다.

👉 문제가 없으므로 그대로 유지한다.

15 추가

삽입 시 노드 내부 데이터는 항상 오름차순 정렬되어야 한다.

👉 여전히 노드가 넘치지 않으므로 그대로 유지한다.

2 추가

2를 넣으면 노드에 들어갈 수 있는 최대 key 개수 m - 1개를 초과한다.

노드 내부 데이터를 오름차순 정렬한다.

가운데 값인 2를 승격(promote)시킨다.

왼쪽(1), 오른쪽(15)으로 노드를 분할(split) 한다.

5 추가

이제부터는 삽입할 때 항상 leaf 노드에 삽입해야 한다.

루트 노드의 값은 2, 삽입할 값은 5

즉, 5 > 2 이므로 오른쪽 자식(15)쪽으로 내려간다.

오른쪽 노드(15)에 5를 넣고, 오름차순 정렬한다.

반복 삽입을 통해 완성되는 B트리의 특징

여러 데이터를 순차적으로 삽입하면서 분할과 승격 과정을 거치다 보면, 결국 아래와 같은 형태의 트리 구조가 만들어진다.

삽입 과정을 거치면서 알 수 있는 B트리의 주요한 특징은 다음과 같다.

1. 모든 리프 노드가 동일한 레벨에 위치한다.

B트리는 항상 균형 잡힌 트리(balanced tree)를 유지한다.

루트에서 모든 리프 노드까지의 깊이는 동일하다.
어떤 노드도 너무 깊거나 얕지 않게 균형을 맞춰준다.
따라서 삽입/삭제가 반복되더라도 트리의 높이가 급격히 커지지 않는다.

2. 평균 / 최악의 탐색 성능 = O(logN)

이 균형 잡힌 구조는 탐색 성능에 큰 이점을 가져다준다.

트리의 높이는 수준으로 얕기 때문에, 탐색 성능이 항상 일정하게 빠르다.

참고 자료

YouTubeBJ.54-1 B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지를 설명합니다! (DB 인덱스과 관련있는 자료 구조)

BJ.54-1 B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지를 설명합니다! (DB 인덱스과 관련있는 자료 구조)

#btree #DB #데이터삽입 #쉬운코드 #백발백중 DB 인덱스 구현에 사용되는 B tree 계열의 자료 구조를 이해하기 위해서는 일단 B tree가 어떤 특징이 있고 어떻게 동작하는지를 아는 것이 중요합니다 이번 영상은 B tree의 개념과 특징, 그리고 데이터를 삽입하게 되면 어떤 식으로 동작하게 되는지를 설명합니다 그럼 오늘도 고고씽! 00:00 인트로 00:11 BST 복습 01:30 자녀 노드를 세 개 가지게 만들려면? 05:04 B tree의 특징 06:47 B tree의 주요 네 가지 파라미터 12:08 B tree 노드의 key 수와 자녀 수의 관계 15:16 B tree 데이터 삽입 관련 두 가지 포인트 16:41 3차 B tree를 예제로 데이터 삽입 배울 예정 17:01 3차 B tree의 데이터 삽입 예제 시작 32:40 B tree의 leaf 노드는 모두 같은 레벨에 있다 34:04 클로징

TISTORY[자료구조] B-tree란? / B-tree의 연산 / B*tree, B+tree / B+tree 구현

[자료구조] B-tree란? / B-tree의 연산 / B*tree, B+tree / B+tree 구현

B-tree란? B-tree는 Self-balanced Tree 중 가장 유명한 자료구조입니다. Balanced-tree를 의미하며, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다. 즉, 하나의 노드에 하나의 데이터를 저장하는 다른 Self-Balanced Tree와 달리, 하나의 노드에 여러개의 데이터를 저장하는 방식으로 Tree의 height를 줄여 탐색 시간을 더 획기적으로 줄이도록 고안된 트리입니다. (B-tree와 B+tree, B*tree가 있지만 일반적으로 B tree라 함은 B-tree를 의미합니다.) 이렇게 고안된 트리를 유지하기 위한 몇가지 규칙이 있습니다. 1. 노드 안에 k개의 데이터가 있다면 자식 노드 수는 k+1개여야 한다. 첫..

product.kyobobook.co.kr