이전 포스팅에서 hash table에 대해 살펴봤습니다. 이번 포스팅을 통해 인덱스에 활용되는 B+Tree 자료구조에 대해 살펴보겠습니다. B+Tree B+Tree는 O(log n)의 시간 복잡도로 삽입, 삭제 및 검색이 가능한 자료구조입니다. 이진 탐색 트리와 다르게 하나의 부모 노드는 여러 자식 노드를 가질 수 있습니다. B+Tree의 특징은 다음과 같습니다. - Perfect balance : 모든 leaf node는 트리 내 동일한 깊이를 가집니다. - 노드가 최대 M개의 자식 노드를 가질 수 있다고 가정하면, 각 노드는 최소 (M/2 -1) ~ (M-1) 개의 키를 가집니다. - Inner node가 k 개의 키를 저장한다고 가정하면 총 k+1 자식 노드(non-null)를 가집니다. B+Tre..