[#2]자료구조(Data Structure) - b+트리에 관해서!

안녕하세요!

관심쟁이 영호입니다.

오늘은 자료구조 공부를 해볼거에요!

---

지난번에 자료구조로 b-트리를 공부하였습니다!

오늘은 b-트리의 후속작(b*트리)의 후속작(b+)를 공부할 예정이에요!

 

b+트리가 b, b*트리랑 이름이 비슷하다고 생각하고 공부하시면 엄청엄청 헷갈려요!

그냥 독단적인놈이라고 생각하고 공부하도록해요 ㅎㅎ

 

 

b+트리?

b+트리는 b트리와는 달라요! 말로 먼저 말씀드리면 루트노드부터 하위노드들은 그냥 방향만 알려주는 척도입니다.

모든 데이터는 LeafNode에 있습니다!

 

그림을 보시죠.

보시는 것과 같이 Root노드에 "16, 25, 40"이 있는데 

LeafNode에 똑같이 "16, 25, 40"이 있는 것을 볼 수 있어요!

 

사실상 B+트리에서 Leaf Node위에 있는 것들은 방향을 알려주는 역할이라고 보시면 됩니다!

그래서 실제로 Leaf Node가 실제 데이터값 이에요.

 

이러한 특성 때문에 삭제 및 삽입이 되어도 위쪽 방향척도값은 

그대로 남아있는 경우가 있어요!

즉, 윗 사진에서 16을 삭제해도 그냥 해당 Key값만 삭제될 뿐

바뀌는게 없어요!

 

※여기서 "16, 25, 40"의 위치는 left, right의 가장 왼쪽-중앙- 가장오른쪽은 임의로 정해줍니다. 

실제로 왼쪽 노드의 가장 오른쪽 위치에 위치시켜요!

이유는 삭제나 구조변경이 있을 때 별도의 포인터작업을 해주지 않아도 되기때문입니다.

 

그럼 어떨때 구조가 바뀔까?

구조가 바뀌는 경우는, 하위 노드에서 Key값이 m개가 넘어버릴때 분할을 해주어야 하는데, 바로 그 때 구조 변경이 생깁니다!

 

다시한번 확실히 정리를 해볼게요!

b+특징

그럼 삽입을 살펴볼게요.

 

b+트리 삽입

m = 3 삽입

방향척도와 같은 값의 데이터는 left노드의 가장 오른쪽에 위치.

 

 

가장먼저 2, 15 삽입

30 삽입후 overflow발생!

중간노드를 상위 노드로 이동 후 배치

10 삽입 후 overflow발생!

똑같은 방식으로 배치

12, 31삽입

36 삽입후 overflow발생!

재배치 했는데 상위 노드에서 overflow 재발생!

했던 그대로 다시 재배치!

 

---

여기까지

b+와 b+의 삽입에 대해서 공부했어요!

잘 이해되셨을까요!?

 

다음에는 삭제, 탐색에 관해서 공부를 해볼게요!

 

혹시나 보시면서 모르는 부분이나 오류가 있는 부분을 보셨다면!

언제든지 댓글로 말씀해주세요.

 

읽어주셔서 감사합니다.

행복한 하루 되세요!