[자료구조] B-tree 알아보기

 

B-tree 알아보기

이진탐색트리(BST)

-각 노드는 최대 2개의 자녀 노드를 가진다.
-모든 노드의 왼쪽 서브 트리는 부모보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 부모보다 큰 값을 가진다.
-삽입,검색,삭제의 평균적인 시간복잡도: O(logN)

-하지만 편향된 트리가되면 최악의 경우 O(N)까지 떨어질 수 있다

 

이진 탐색트리의 문제점

-깊이가 깊어지면 검색, 삽입성능이 떨어진다.

-균형유지가 어렵다.

 

 

 

 

자녀노드를 더 많이 갖기위해서는 어떻게 해야하는가?

-> 상위 노드에 더 많은 키값을 가지면 된다.

예를들어 자녀 노드를 3개씩 갖기위해서는 부모 노드에 2개의 키값을 가져야한다. 2개의 키 값이 있다면 3가지 값의 범위를 만들어 낼 수 있기 때문. ( <k1, k1< < k2, >k2)

왼쪽자식: 작은 키값보다 작은값
중간자식: 작은 키값보다 크고 큰 키값보다 작은 값
오른쪽자신: 큰 키값보다 큰 값

 

자녀노드의 최대개수를 늘리기 위해서 부모노드에 키를 하나 이상 저장한다.
그리고 부모 노드의 키들을 오름차순으로 정렬한다

 

B tree

이처럼 B tree구조는 1개 이상의 키값을 가질 수 있어서 최대 자식의 수를 늘릴 수 있다. 

 

각 노드의 키들은 오름차순으로 정렬된다.

이진탐색트리는 자녀를 최대 2개까지만 가질 수 있는 것에 반해 B tree는 최대로 가질 수 있는 자식 노드를 원하는 만큼 가질 수 있다
(Binary Search Tree를 일반화한 트리이다. 개념을 더 확장해서 더 많은 자식과 데이터를 저장할 수 있도록 하였다.)

최대 몇 개의 자녀 노드를 가질 것인지가 B tree를 사용할 때 중요한 파라미터

 

M : 각 노드의 최대 자녀노드 수
(최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라 부른다)

M-1 : 각 노드의 최대 키 수

M/2(올림) : 각 노드의 최소 자녀 노드 수 (루트노드, 리프노드 제외)

M/2(올림)-1 : 각 노드의 최소 키 수(루트 노드 제외)

 

-B tree 내부 노드의 키 수가 x개라면 자녀 노드의 수는 언제나 x+1 개다.

-노드가 최소 하나의 키는 가지기 때문에 몇 차 B tree 인지와 상관없이 내부 노드는 최소 두 개의 자녀는 가진다
(최소 자녀 수:M/2(올림))

 

B tree 데이터 삽입 방식

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

2. 노드가 넘치면 가운데 키를 기준으로 좌우 키들은 분할하고 가운데 키는 승진한다.

 

 

 

 

*B-tree의 특징과 이진탐색트리(BST)의 차이점

1. 이진탐색트리는 자식노드를 최대 2개까지 가지지만 B-tree는 1개이상의 키값으로 자식노드를 여러개 가질 수 있다.

(B-tree가 최대 M개의 자식노드를 가질 수 있을 때, 키값은 M-1개 까지 갖게된다)

 

2. 이진탐색트리는 깊이가 깊어질 수 있지만 B-tree는 넓게 퍼지면서 높이를 낮춘다.(balanced tree -> 모든 leaf노드들이 같은레벨에 있음)

(각 노드가 여러개의 키값을 저장해서 높이가 낮아지고 검색속도가 향상된다 -> DB 인덱스에 사용되는 이유)

 

-> 그 결과 B-tree의 높이는 항상 logN으로 유지되어 항상 일정한 성능을 유지할 수 있다

(이진탐색트리는 balanced tree가 아니라서 한쪽으로만 기울어질 수도 있는데 최악의 경우 O(N)의 시간복잡도를 갖게될 수도 있다.)

 

 

 

 

B tree계열을 DB인덱스로 사용하는 이유

-DB는 기본적으로 secondary storage에 저장된다

-B tree indexes self-balancing BST에 비해 secondary storage 접근을 적게한다.

-B tree노드는 block단위의 저장공간을 알차게 사용할 수 있다.

 

Hash index를 쓰지않는 이유

Hash index는 삽입/삭제/조회의 시간 복잡도가 O(1)이지만 equality(=) 조회만 가능하고 범위 기반 검색이나 정렬에는 사용될 수 없다는 단점이 있다.