자료구조 ㅣ [#1] b-트리

안녕하세요.

관심쟁이 영호입니다!

 

오늘 공부한 내용은

트리 응용인데요!

 

같이 한번 보시죠!

---

b-트리는

Balanced Tree의 일종인데요!

 

기존의 이진트리처럼 노드를 양쪽에 두개를 달고있는 모양과는 달라요!

(2-3-4트리와 비슷하다고 생각합니다!)

 

b트리

다음 그림처럼 생각해보시면 편해요!

 

그림에서 볼 수 있듯이 기존의 트리처럼 node내의 key값이 하나만 있는게 아니에요!

여러개가 있는걸 확인할 수 있습니다.

 

 

 

이러한 트리에도 제약조건이 있어요!

 

1. 디스크의 접근 단위는 블록(페이지)입니다.

-트리로 저장된 데이터에 접근할 때 데이터를 받아오는 수는 블록 단위로 한다는 뜻이에요! 위의 그림과 같이 해놓았는데 데이터 하나씩만 받아오면 블록단위로 묶어둔 이유가 없죠 ㅠ

 

2. 각 Node는 최대 m(포인터의 갯수), 최소 m/2개의 sub-tree를 가져야 한다.

- 이 말의 뜻은 첫번째로 블록속에 한 데이터가 있으면 left, right라는 포인터를 가지고 있자나요!  그래서 자식노드는 최대로 포인터의 갯수인 m개까지 가지고 있을 수 있다는 뜻입니다.

 

- 두번째로 m/2개의 갯수만큼 가질 수 있다는 뜻이에요! 

 

3. 모든 LeafNode는 같은 Level에 있어야 한다.

 

4. 각 LeafNode의 Key값의 갯수는 최소 (m/2) -1개, 최대 m-1개 이다.

노드 속에 있는 데이터들의 갯수를 말하는거에요! 포인터가 10라고 하면 최소 4개 최대 9개를 가지고 있을 수 있다는 뜻입니다.

 

5. 추가되는 모든 key값은 노드내에서 왼쪽에 추가가 됩니다.

 

삽입

그럼 m=5인 b트리를 만들어볼게요.

 

삽입순서 : 1 9 3 5 29 2 16 13 27 4 6 8 14 12 30 7 15 24

총 18개

 

m = 5라서 4개까지는 그냥 들어갑니다!

29가 들어가게되면 overflow가 발생합니다!

그래서 중간값인 "5"를 위로 올려줍니다.

2, 16, 13을 넣어도 overflow가 발생하지 않습니다.

 

27을 넣으니 overflow가 발생하여

"16"을 위에 노드로 이동해주고

16보다 낮은 key들을 5와 16사이에 위치시켜줍니다.

4를 삽입해줍니다.

12, 30, 7, 15, 24를 삽입해줍니다.

14를 삽입했더니 overflow가 발생합니다.

가운데 값인 "9"를 윗노드로 이동시켜줍니다.

 

12, 30, 7, 15, 24를 삽입해줍니다.

 

제가 직접 그린거라.. 쓰다가 오타가 좀났어요..ㅋㅋ

이런식으로 되는겁니다!

 

여기서 윗노드로 이동해주었을 때

윗노드에서 다시 overflow가 발생할 수 있어요!

그렇게 될 경우에는 다시 분할작업을 해주어야합니다.

 

여기서는 m이 홀수라서 가운데값을 윗노드로 이동해주었는데요!

m이 짝수일 경우에는 중간값보다 바로 한단계낮은 값을 올려주는 방식으로 하여야 합니다.

 

---

 

 

여기까지 b트리와 b트리의 생성 및 삽입에 대해서 다루어 보았는데요!

저도 공부하고 있는지라.. 오류가 있을 수 있어요!

혹시나 오류를 발견하시면 언제든지 댓글로 말씀해주세요.

수정하도록 하겠습니다.

 

다음은 삭제에 대해서 해보겠습니다!