[OS] 책 설명이 x같아서 내가 쉽게 쓴 B 트리

 파일 처리 시험 공부를 하다가 너무 말이 어려워서 저만의 방식으로 다시 정리해봤습니다. 왜 말을 그렇게 어렵게 쓰는지...

 

일단 B트리가 뭔지 알아보자.

 

 

●B 트리 개요

 

(1) B 트리의 정의 : B 트리는 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조 이다.

 

 그냥 한 마디로 데이터를 쉽게 다룰 수 있게 하는 자료 구조의 일종이다.

 

그렇다면 왜 B 트리를 쓰는가 ? B 트리는 Balanced- Tree 의 일종으로 트리의 균형이 맞다. 즉 트리내에서 삽입과 삭제가 일어나더라도 최대한 균형있는 트리 형태를 유지하여 이진 탐색의 장점을 살린 트리다.

 

 

균형이 맞춰진 트리의 장점이 뭘까? 바로 이진 탐색을 활용할 수 있다는 점이다.
아래는 편향 트리이다. 편향 트리란 한 쪽 방향으로만 노드가 뻗어나가있는 트리 구조를 말한다.
편향 트리 구조를 이용해서 데이터를 저장하고 검색을 한다고 하자.결론적으로 순차 검색과 다를바가 없는 O(n) 시간의 검색 시간을 갖게 된다. 한 마디로 모든 노드를 하나하나 다 보면서 원하는 키 값을 찾는 검색을 한다는 뜻이다. 효율이 극히 떨어진다.

편향 트리

 

 

 

 하지만 균형이 갖춰진 트리라면 O(log n) 시간의 검색 시간을 갖는다. B트리도 이러한 균형 트리의 일종이다.

 

 

균형 트리

 

 

 

 

 그렇다면 균형 트리의 일종인 B 트리만의 특징은 무엇일까?

 

 

B 트리는 하나의 노드에 여러 자료가 배치되는 트리구조 이다. 만약 한 노드에 M개의 자료가 배치되면 M차 B 트리 라고 명명할 수 있다.

 

 

 

B 트리의 특징

① 노드의 자료수가 K 이라면, 자식의 수는 K + 1 개이어야 한다.   ② 자료는 정렬된 상태로 저장된다.   ③ 한 노드 N 의 왼쪽 서브트리는 N의 키 작은 값으로 되어 있고, 오른쪽 서브트리는 큰 값으로 되어 있다.    ④ ROOT 노드는 적어도 2개 이상의 자식을 가져야한다. ( 트리가 ROOT 노드로만 구성되어있을 경우 예외, 위의 특징 ① 때문에)   ⑤ ROOT 노드를 제외한 모든 노드는 적어도 ⌊ M/2 ⌋ 개의 키를 가지고 있어야 한다. ( ⌊ ⌋ : floor function - 소수점을 버린다.) (B 트리의 장점 - 저장 장치의 효율성, 즉 각 노드마다 반 이상 키 값이 저장되어 있다.)   ⑦ 리프노드로 가는 경로의 길이는 모두 같다 = 리프노드는 모두 같은 레벨에 있다.   ⑥ 입력 자료는 중복될 수 없다.

 

 

 

위의 특징을 정확히 알고 검색, 삽입과 삭제를 알아볼게요~

 

 

(2) B 트리의 검색

 

- 검색은 정말 간단하다. 위에서 언급했듯 이진 탐색을 원하는 키 갑을 검색할 수 있다. O(log n)

- 중위 순회를 통한 순차 탐색도 가능한데 이건 성능이 나쁘다.(=> B+ 트리)

 

 

(3) B 트리의 삽입

 

 

B 트리의 삽입

① 자료는 항상 리프(Leaf) 노드에 추가 된다.   ② 리프 노드의 선택은 ROOT 노드부터 시작해 하향식으로 탐색하며 결정한다.   ③ 선택한 리프 노드에 여유가 있다면 그냥 삽입. 여유가 없다면 분할한다.

 

 

삽입 예제를 놓고 한 번 상세하게 볼게요~

 

아래 예제에서 6을 삽입해볼게요. 

 

 

 

5차 B트리 가정

 

자신이 가진 키 값의 갯수를 N이라고 할 때 모든 부모 노드는 N+1개의 자식을 가지고 있다고 가정 

 

 

우선 Case 1.  리프 노드가 꽉 차있었을 경우

리프 노드에 5개의 키 값이 모두 차서 들어 갈 수 없는 상황

 

부모 노드의 키 값의 갯수가 5개가 아니어서 더 들어갈 수 있는 상황.

리프 노드의 중간값인 3을 올려주고 노드를 2개로 분할해줍니다. 그리고 6을 삽입!

 

 

 

 

 

 

 

 

case 2. 부모 노드가 꽉 차있을 때

부모 노드가 꽉 차있을 때 6을 삽입해보자

 

 

 

 

 

 

일단 부모 노드를 2개의 노드로 분할해준다.

 

그리고 나서 case 1 처럼 3을 부모로 올리고 리프 노드를 2개로 분할한 뒤 6을 삽입한다.

 

 

 

 

이와 같은 방식으로 삽입을 할 수 있어요!

 

 

 

 

 

 

(4) B 트리의 삭제

 

B 트리의 삭제

① 삭제할려는 키 값을 가진 노드가 가지고 있는 키 갯수를 해당 키 값 삭제 후에 M/2 개 이상이 되도록 해야한다.   ② 형제한테 빌리기 / 형제와 결합하기 ( 아래서 자세히 설명 )   ③ 삭제 키가 있는 노드가 내부 노드인 경우 - 대체 키를 찾아 대체한다.( 왼쪽 서브트리 중 가장 큰 값 OR 오른쪽 서브트리 중 가장 작은 값.)

 

 

 

Case 1 . 리프 노드에서 삭제하기

 

5차 B 트리 가정

 

2를 삭제해보자!!

 

일단 2를 그대로 삭제하게 되면 왼쪽 서브트리의 키 값의 갯수가 1개밖에 남지 않아 5차 B 트리에서 모든 노드는 2개 이상의 키를 가져야 한다는 성질에 위배된다. 따라서 형제 노드에서 값을 빌려와야한다. 그런데 4를 빌려오게 되면 부모인 3에 위배된다.( 왼쪽 서브트리는 3보다 작은 값만 와야하기 때문이다.

 

 

그래서 4를 위로 부모로 올리고 3을 왼쪽 서브트리로 내리는 방법으로 트리를 변형한다.

그리고 2를 삭제한다.

 

 

 

 

 

 

만약 아래의 경우라면 어떻게 해야할까?

 

 

 

 

상황을 보면 2를 삭제해야하는데 1이 혼자 남게되어 언더플로 현상이 일어난다. 그래서 형제 노드에서 빌려오자니 4를 가져올 때 부모 노드인 3에 위배된다. 뿐만아니라 4를 가져간다 하더라도 5가 혼자 남게되어 언더 플로 현상이 일어난다.

 

 

따라서 위 그림처럼 부모인 3을 가져와 한 노드로 만든 후 2를 삭제한다.

 

 

 

 

Case 2. 내부 노드에서 삭제하기

 

 

방법은 대체키를 찾아서 삭제하면 됩니다.

 

위에 적어논 방법중 3번째 방법을 사용해요.

 

 ③ 삭제 키가 있는 노드가 내부 노드인 경우 - 대체 키를 찾아 대체한다.( 왼쪽 서브트리 중 가장 큰 값 OR 오른쪽 서브트리 중 가장 작은 값.)

 

 

아래 예시를 볼게요.

 

이런식으로 5차 B트리가 주어졌을 때 만약 9를 삭제하고 싶다면

 

(1) 노드의 왼쪽 서브 트리에서 가장 큰 값인 8 혹은 오른쪽 서브 트리에서 가장 작은 값은 10으로 바꿔주고 9를 삭제하면 돼요.

 

 

 

초기 상태

 

9와 10을 바꿔줘요.

 

그 다음 9를 삭제해주면 B트리의 성질을 유지하면서 키 값을 삭제 할 수 있어요~