DB - indexing(1)

Notice

Recent Posts

Recent Comments

Link

« 2025/05 »
일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

티끌모아 태산

DB - indexing(1) 본문

CS 지식/데이터베이스

DB - indexing(1)

goldpig 2023. 12. 5. 19:48

728x90

이번 시간에는 B tree의 개념과 특징 그리고 데이터 삽입이 어떻게 동작하는지를 배워보겠습니다. -> DB 인덱스와 관련있는 자료구조!

B tree 개념과 특징

B tree를 공부하기 전에 이진 탐색 트리(BST)에 대해서 알아보겠습니다. BST의 특징은 다음과 같습니다.

모든 노드(Node)의 왼쪽 sub-tree는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 sub-tree는 해당 노드의 값보다 큰 값들만 가집니다.

자녀 노드는 최대 두 개까지 가능하다.

그런데 자녀 노드를 세 개까지 갖고 싶으면?! 즉, 다음과 같이 자녀가 3명인 형태를 갖고싶으면 어떻게 해야할까요?

BST의 대소 비교 아이디어를 적용해보면 부모 노드는 하나의 값만 갖는게 아니라 K1과 K2값을 갖도록 해야합니다.

예를들어, 부모 노드에 50과 80이라는 값이 들어있다고 했을 때, 다음과 같이 임의의 값을 가진 자식 노드를 가질 수 있습니다.

이를 Tree로 확장해서 생각해 볼 수 있습니다.

지금까지 배운 내용을 바탕으로 정리 해보겠습니다. 결국, 자녀 노드의 최대 개수를 늘리기 위해서는 부모 노드의 key를 하나 이상 저장해야 합니다. 그리고 부모 노드의 key들을 오름차순으로 정렬해서 저장해 주어야합니다. 이렇게 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정됩니다. 따라서 이러한 형태로 구성되어 있는 트리를 B tree 라고합니다. 그래서 자녀 노드의 최대 개수를 입맛에 맞게 결정해서 쓸 수 있습니다. -> BST를 일반화한 트리를 B tree

그러면 자녀의 개수를 우리가 정할 수 있다고 했는데 "최대 몇 개의 자녀 노드를 가질 것인가? " 가 B tree를 사용할 때 중요한 파리미터가 됩니다.

B tree parameter

M: 각 노드의 최대 자녀 노드 수 (가장 중요!), 그래서 최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라 부른다 그래서 위의 사진에서 예를들면, 3차 B tree라고 합니다.
M - 1: 각 노드의 최대 key 수
[M/2]: 각 노드의 최소 자녀 노드수입니다. 이때 주의할 점은 M/2를 한 후 올림을 해주어야합니다. *Root node and Leaf node(자녀 노드가 없는 노드)는 제외! -> internal node.
[M/2] - 1: 각 노드의 최소 key 수 입니다. *root node제외! *leaf node: [M-1/2]

또 다른 특징을 살펴보면 다음과 형태는 B tree가 될 수 없습니다. 왜냐하면 internal node의 key 수가 x개라면 자녀 노드의 수는 언제나 x + 1개 이어야 합니다. 그래서 아래 형태는 자녀의 개수가 3개이여야 하는데 2개이므로 적절하지 않습니다.

그래서 다음과 같은 형태에서도 조건을 위반하기 때문에 B tree라고 할 수 없습니다. internal node의 key가 1개 이므로 자녀 노드는 언제나 1 + 1인 2가 되어야 합니다. 아래는 자녀가 3개 이기 때문에 올바르지 않습니다.

그래서 정리해보면 다음과 같은 특징을 알 수 있습니다.

internal node의 key 수가 x 개라면 자녀 노드의 수는 언제나 x+1 개가 됩니다.
노드가 최소 하나의 key는 가지기 때문에 몇 차 B tree 인지와 상관없이 internal node는 최소 2개의 자녀를 갖습니다.
M이 정해지면 root 노드를 제외하고 internal node는 최소 [M/2]개의 자녀 노드를 가질 수 있게 됩니다.

예를들어, 5차 B tree라고 했을 때, root node를 제외하고 모든 internal node는 최소 3개의 자녀를 갖습니다.

B tree 데이터 삽입

데이터 추가: 1, 15, 2, 5, 30, 90, 20, 7, 9, 8, 50, 70, 60, 40

데이터의 추가는 항상 leaf 노드에 합니다.
노드가 넘치면 가운데(median) key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진합니다. 이때 노드가 넘친다는 뜻은, 각 노드가 가질 수 있는 최대 자녀 노드수를 넘어서는 것을 말합니다.

예를들어, 3차 B tree 데이터 삽입에 대해서 동작 방식을 알아보도록 하겠습니다. 반드시 기억해야할 사항이 데이터 추가는 leaf 노드에 한다는 것과 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진시킨다는 것입니다.

먼저, 1을 추가 해 보겠습니다. 현재 아무것도 없기 때문에 Root 노드를 만들고 거기에 1을 추가 하겠습니다.

그리고 여기서 담을 수 있는 공간이 2개임(2개의 key를 저장할 수 있는 공간)을 알 수 있는데, 이는 M = 3이기 때문에 최대 key값이 3 - 1 = 2이기 때문입니다. 다음으로, 15를 추가해 보겠습니다. 추가는 leaf노드에 한다고 했지만 현재 root노드가 root이면서 동시에 leaf노드이기 때문에 15를 1옆에 추가 줍니다.

이어서 2를 추가해 보겠습니다. 일단은 root 노드가 leaf노드 이기 때문에 삽입을 하고 오름 차순으로 저장을 합니다.

여기서 노드가 넘치는 상황이 발생하기 때문에 가운데 키를 기준으로 좌우 key들은 분할하고 가운데 key는 승진 시킵니다.

화살표는 자녀 노드를 가리키는 pointer 역할을 합니다. 자 그러면 이번에는 5를 추가 해 보겠습니다. 추가는 leaf노드에 해야합니다. 우선, root 노드부터 조회를 시작해서 대소 비교를 통해 어느쪽 자녀 노드로 갈 지 정해야 합니다. 그리고 저장할 때는 오름 차순으로 정렬된 상태로 저장을 해주어야 합니다.

이제는 30을 추가해 보겠습니다. root 노드부터 조회를 시작해서 오른 쪽 자녀 노드에 오름차순으로 저장합니다. 그러면 노드가 넘치는 문제가 발생해서 가운데 key 값을 기준으로 좌우 key를 분할하고 가운데 key는 한 단계 승진시키는 방식을 택합니다.