B Tree

하나의 노드에 여러요소가 존재할 수 있는 자료구조

[MySQL] B-tree, B+tree란? (인덱스와 연관지어서)

B-Tree

정렬된 상태로 저장된다는 점에서 BST와 유사하지만 한 노드 당 자식 노드가 2개 이상이다.

어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있는(log N) 사기 자료구조

그런 사기 자료구조 답게 삽입 및 삭제 과정이 복잡하다

B-Tree Visualization

재미있음!

B-Tree - 삽입

[자료구조] 그림으로 알아보는 B-Tree

차이점

  1. B-Tree의 각 노드에는 key뿐만 아니라 data도 들어갈 수 있다

    B+Tree의 각 노드에는 key만이, data는 리프 노드에만 들어갈 수 있다

  2. B+Tree의 리프 노드는 linked list로 연결되어 있다

규칙