[DB] B tree 전체 정리

참고 자료 

유투브 쉬운코드 B tree

이진 탐색 트리 (BST)

https://20240228.tistory.com/87

[BinarySearchTree] 이진 검색 트리

BST에 대해서 생소하면 해당 링크를 참고하자 

 

BST example

 

모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다

 

자녀 노드는 최대 2개 

 

자녀 노드를 세 개 가지게 만드려면?

자녀 노드를 3개 가지는 트리를 만들려면 부모 노드는 1개의 값만 가져서는 안된다

 

                    50 | 80

   

 ? < 50     50 < ? < 80   ? > 80

 

이런 방식으로 전체 트리를 확장할 수 있다. 

 

정리 

자녀 노드의 최대 개수를 늘리기 위해서 

부모 노드에 KEY를 하나 이상 저장한다

부모 노드의 KEY들을 오름차순으로 정렬한다

정렬된 순서에 따라 자녀 노드들의 KEY 값의 범위가 결정된다

 

이런 트리를 B tree 라고 한다. 

B tree 특징 

BST 복습에서 정리했던 방식을 사용하면 자녀 노드의 최대 개수를 입맛에 맞게 결정해서 쓸 수 있다

B tree는 BST를 일반화한 tree

 

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

B tree 파라미터 

M: 각 노드의 최대 자녀 노드 수 (차수)

최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라 부른다 

 

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

M차수에 의해서 알아서 결정된다.

ex) 3차 B tree는 각 노드의 최대 key 수는 2이다.

 

M/2: 각 노드의 최소 자녀 노드 수 

M차수에 의해서 알아서 결정된다.

이때 M/2는 올림처리 

이 조건은 root node, leaf node 제외 

 

M/2 - 1: 각 노드의 최소 key 수 

M차수에 의해서 알아서 결정된다.

M/2 이후 올림 처리하고 1을 뺀다. 

이 조건은 root node 제외 

 

internal(root, leaf x)노드의 key 수가 x 개라면 자녀 노드의 수는 언제나 x + 1 개다

노드가 최소 하나의 key는 가지기 때문에 몇 차 B tree 인지와 상관없이 internal 노드는 최소 두 개의 자녀는 가진다 

B tree 데이터 삽입 (3차 B tree)

추가는 항상 leaf 노드에 한다

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

 

1, 15 추가 

 

2 추가 

1, 2, 15 (항상 key는 정렬된 상태)

 

현재 노드에 key 개수(3) > 노드의 최대 key 개수: (자식 노드의 최대 개수(M차) - 1) (2) 이다.

 

그래서 가운데 key를 기준으로 (1, 15)분할하고 가운데 key 2는 승진한다.

 

5 추가 

5를 추가하려면 B tree를 조회해야 한다.

조회는 root 노드에서 시작한다. 

 

5는 2보다 크니까 오른쪽 노드로 간다. 

해당 노드의 key에 5를 추가한다.

 

30 추가

30를 추가하려면 B tree를 조회해야 한다.

조회는 root 노드에서 시작한다. 

 

30은 2보다 크니까 오른쪽 노드로 간다.

해당 노드에 key에 30을 추가한다. 

5, 15, 30

 

키의 개수가 2를 넘어간다. 

마찬가지로 가운데 key인 15를 승진 시키고 나머지 2개의 key는 분할한다. 

 

90 추가

 

20 추가

 

20을 추가하려면 root 노드에서 조회를 시작한다. 

그럼 2,15 보다 크니까 오른쪽 노드인 [30, 90] 노드로 이동한다. 

 

→ [20, 30, 90] 

분할 작업 진행 

현재 루트 노드에도 분할 작업을 진행 

 

 

7 추가 

 

9 추가 

 

8 추가 

 

10 추가 

 

특징 정리 

모든 leaf 노드들은 같은 레벨이 있다.

→ balanced tree (균형 트리)

BST는 최악의 경우 O(N)이다. 이유: 한쪽으로만 치우친 트리

하지만 B tree는 balanced tree여서 최악의 경우도 O(logN)이다. 

즉, 이런 특징은 항상 동일한 성능의 조회가 가능하다는 것을 알 수 있다. 

B tree 데이터 삭제 (3차 B tree)

삭제도 항상 leaf 노드에서 발생

삭제 후 최소 key 수보다 적어졌다면 재조정한다 

1. key 수가 여유있는 형제의 지원을 받는다.

2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.

3. 2번 이후 부모에 문제가 있다면 거기서 다시 재조정한다. 

3.1 부모가 root 노드고 비어있다면  부모 노드들 삭제한다 직전에 합쳐진 노드가 root 노드가 된다

3.2 부모가 root 노드가 아니라면  그 위치에서 부터 다시 1번부터 재조정을 시작한다 

 

 

M = 3

M / 2 = 1.5 → 1.5 올림 = 2

2 - 1 = 1

3차 B tree에서 각 노드의 최소 key 수: 1

 

시작 데이터 

 

6 삭제

6을 삭제하려면 먼저 6을 조회해야 한다. 

조회는 항상 루트 노드에서 시작한다. 

 

루트 노드에 6은 존재하지 않는다. 

6은 루트 노드에 있는 KEY인 15 보다 작으니까 왼쪽 노드(서브 트리)로 이동한다. 

 

노드 [3, 7] 

6은 3보다 크고 7보다 작다 

 

가운데 노드(서브 트리)로 이동한다. 

 

노드 [5, 6]

현재 노드에 6이 존재한다. 

 

삭제를 하면 노드는 [5, ]가 된다. 각 노드의 최소 key 수는 1을 만족한다. 

 

5 삭제

루트 노드에 5는 존재하지 않는다. 

5는 15보다 작으니까 왼쪽 노드로 이동한다. 

 

[3,7] 

5는 3보다 크고 7보다 작다. 

가운데 노드로 이동한다.

 

[5, ]

현재 노드는 리프 노드이고 5가 존재한다. 

해당 노드에서 5를 삭제한다.  [ , ]

삭제를 하니까 현재 노드가 최소 key 개수인 1보다 작다. 

5를 삭제한 이후이다. 

 

현재 같은 부모 [3, 7]의 왼쪽 형제 노드 [1, 2]에 여유가 있다. 

왼쪽 노드 개수 [1, 2] = 2 > 1 (각 노드의 최소 key 개수)

 

바로 2를 가운데 노드에 넣으면 좋지만 그럼 B tree 구조가 깨진다. 

그래서 부모 노드의 왼쪽 key인 3을 가운데 노드로 옮기고 형제 노드의 2를 부모 노드에 옮긴다.

 

3 삭제

루트 노드에서 조회 시작 3이 없다. 

15보다 3은 작으니까 왼쪽 노드로 이동한다.  [2, 7]

[2, 7] 노드에도 3은 없다. 

3은 2보다 크고 7보다 작으니까 가운데 노드로 이동한다. [3, ]

 

3을 삭제하면 해당 노드는 최소 key 개수보다 적어진다. 

즉, 재조정이 필요하다.

왼쪽 형제 노드는 [1, ] 여유가 없고 오른쪽 노드는 [8, 9] 여서 여유가 있다. 

부모 노드의 7을 가운데 자식 노드로 옮기고 8을 부모 노드로 옮긴다.

 

7 삭제

조회는 이제 생략 

7을 삭제하면 해당 노드는 최소 key 개수를 위반한다. [ , ]

양 옆의 형제 노드 또한 여유가 없다.

그럼 부모의 지원을 받고 형제를 합친다. 

internal 노드 데이터 삭제 

internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다. 

그렇다면 leaf 노드에 있는 데이터 중에 어떤 데이터와 위치를 바꿔줄 것인가?

삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.

선임자: 나보다 작은 데이터들 중 가장 큰 데이터

후임자: 나보다 큰 데이터들 중 가장 작은 데이터

 

15를 삭제하려면 9(선임자)나 20(후임자)과 위치를 바꿔주면 된다.

이렇게 바꾸면 B tree 구조가 유지되면서 데이터 삭제가 가능하다.

선임자 or 후임자의 위치는 항상 leaf 노드에 있다.

 

즉 B tree 구조의 삭제는 internal 노드의 삭제든 leaf 노드의 삭제든 삭제의 시작은 항상 leaf 노드에서 시작한다.

왜 DB Index로 B tree 계열이 사용되는가?

B tree 계열이란 B tree 구조를 확장하고 개선한 구조를 말한다.

ex) B+ tree, B* tree

 

B+ tree, B* tree의 조회/삽입/삭제 , avg(평균) case / worst(최악) case 모두 O(logN)이 걸린다. 

 

반면 BST는 조회/삽입/삭제의 avg case는 O(logN)이지만 worst case는 O(N)이다. 

왜냐하면 BST는 B tree 와 다르게 balance tree 구조를 보장하지 못한다.

 

ex) 1, 2, 3, 4, 5, 6, 7, 8, 9 이렇게 삽입하면 편향 트리 구조 

1
 \
  2
   \
    3
     \
      ...
       \
        9

 

그래서 AVL tree, Red-Black tree 같은 self-balancing BST가 등장한다. (자가 균형 트리)

해당 자료구조의 시간 복잡도는 B tree 계열과 동일하게 O(logN)이다. 

 

시간복잡도는 동일한데 그렇다면  INDEX에는 왜 B tree 구조를 사용할까?

computer system 

CPU

프로그램 코드가 실제로 실행되는 위치 

 

Main Memory(RAM)

실행 중인 프로그램의 코드들과 코드 실행에 필요한 혹은 그 결과로 나온 데이터들이 상주하는 곳

휘발성 데이터

 

Secondary Storage(SSD or HDD)

프로그램과 데이터가 영구적으로 저장되는 위치 

실행 중인 프로그램의 데이터 일부가 임시 저장되는 곳(RAM 용량이 적어서)

비 휘발성 데이터 

 

DB 데이터는 Secondary Storage에 저장한다.

Secondary Storage는 데이터 처리 속도가 가장 느리다 

 

Secondary Storage는 데이터를 저장하는 용량은 가장 크다 

Secondary Storage는 block 단위로 데이터를 읽고 쓴다 

 

block?

file system이 데이터를 읽고 쓰는 논리적인 단위 

block의 크기는 2의 승수로 표현

대표적인 block size는 4KB, 8KB, 16KB 등이 있다. 

 

즉 읽고싶은 데이터만 읽는 게 아닌 읽고싶은 데이터를 포함하는 block 전체를 읽는다. 

이런 block 단위 데이터 읽기는 불필요한 데이터까지 읽어올 가능성이 있다. 

 

DB 관점에서 Secondary Storage 

DB 데이터는 영구적으로 저장 

DB 데이터는 용량이 크다

 

Main Memory에 있는 데이터로 처리가 가능하면 바로 처리 

Main Memory에 있는 데이터에 없는 데이터가 필요하면 Secondary Storage에 있는 데이터를 MainMemory로 가져온다. (InnoDB)

 

DB에서 데이터를 조회할 때 Secondary Storage에 최대한 적게 접근하는 것이 성능 면에서 좋다 

 

ex) DB 조회를 할 때 Secondary Storage 2번 접근 VS 5번 접근? 

당연히 2번 접근이 성능상 좋다 

 

block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있다

 

인덱스로 성능 비교 (OK 테이블을 조회하자 )

 

시나리오

OK 테이블의 데이터를 조회한다. 이때 where 조건에 b 컬럼 사용

조회 성능을 내기 위해서 인덱스를 생성한다. CREATE INDEX(b)

인덱스 생성은 AVL tree index(b) VS B tree index(b)

tree 각 노드는 서로 다른 block에 있다고 가정 

초기에는 root 노드를 제외한 모든 노드는 secondary stroage에 있다고 가정 

 

AVL tree INDEX(b)

 

루트 노드 (6)을 제외하고 나머지 노드는 Secondary Storage에 있다.

where b = 5; 

b 컬럼이 5인 튜플을 찾으려면 총 4번의 Secnoday Storage에 접근한다.

 

5차 B tree INDEX(b)

 

where b = 5; 

b 컬럼이 5인 튜플을 찾으려면 총 2번의 Secnoday Storage에 접근한다.

 

AVL tree INDEX(b) vs 5차 B tree INDEX(b) 성능 정리 

 

Secondary Storage 접근 횟수

4 vs 2

이는 성능적인 측면에서 5차 B tree 인덱스가 훨씬 빠르다. 

 

탐색 범위

AVL tree는 탐색 범위를 1/2로 줄이지만

5차 B tree는 자식 노드의 최소 ~ 최대 개수 (3 ~ 5) 

최소 1/3 or 최대 1/5 까지 줄이는게 가능하다.

즉, 5차 B tree가 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있다.

 

노드의 데이터 수 

AVL tree는 각 노드의 데이터 수는 1개로 고정

반면 5차 B tree는 각 노드의 데이터 수는 최소2개에서 최대 4개이다. 

이는 Secondary Storage에서 block 단위로 데이터를 가져오기 때문에 

5차 B tree는 DB에서 사용할 데이터를 가져올 가능성이 AVL tree에 비해서 더 많다.

DB에서 사용하는 데이터는 이미 노드에 포함되어 있을 확률이 높아 추가적인 I/O를 줄일 수 있다.

이는 block 단위에 대한 저장 공간 활용도가 더 좋다. 

B tree의 강력함 (101차 B tree)

101차 B bree는 자식의 개수를 최대 101개 가지는 것이다. 

즉 각 노드의 최대 데이터 수는 100이다.

 

101차 B tree 파라미터 정리 

최대 자식 수 : 101

최대 key 수: (101 - 1) = 100

최소 자식 수: (101 / 2) 올림 = 51 (root 제외)

최소 key 수: (101 / 2) 올림 - 1 = 50  (root, leaf 제외)

 

101차 B tree best case 

level0: 노드 수: 1                             데이터 수: 100(최대 key 수)

level1: 노드 수:101(최대 자식 수)   데이터 수: 101 * 100 

level2: 노드 수: 101^2                    데이터 수: 101^2 * 100

level3: 노드 수: 101^3                    데이터 수: 101^3 * 100

 

level3까지의 적재 가능한 데이터 수: 104060400 (1억..?)

 

101차 B tree worst case 

level0: 노드 수: 1                               데이터 수: 1

level1: 노드 수:2                                데이터 수: 2 * 50 (최소 key 수)

level2: 노드 수: 2 * 51(최소 자식 수) 데이터 수: 2 * 51 * 50 

level3: 노드 수: 2 * 51^2                    데이터 수: 2 * 51^2 * 50

 

level3까지의 적재 가능한 데이터 수: 265301

 

101차 B tree avg case

265301 < 전체 데이터 수 < 104060400

네 개의 level 만으로 수 백만, 수 천만 개의 데이터를 저장할 수 있다

root 노드에서 가장 멀리 있는 데이터도 세 번의 이동만으로 접근할 수 있다 

 

정리 

Secondary Storage 접근 횟수도 적은데 데이터 저장량도 많다.

B tree는 정말 강력한 자료구조구나....

정리

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

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

 

hash index 사용은?

hash index는 삽입/삭제/조회의 시간 복잡도가 O(1)이지만 equality(=) 조회만 가능하고 

범위 기반 검색이나 정렬에는 사용될 수 없다는 단점이 있다.