이전 포스팅에서 B+Tree에 대해 살펴봤습니다. 이번 포스팅에서는 인덱스 동시성 문제를 어떻게 해결하는지 살펴보겠습니다. Concurrency Control 여태까지 논의했던 B+Tree는 단일 스레드 환경에서만 정상적으로 동작합니다. 멀티 스레드 환경에서는 두 개 이상의 스레드가 동일한 노드에 동시에 접근할 수 있습니다. DBMS는 concurrency control protocol을 통해 동시에 접근되는 데이터를 물리적 또는 논리적으로 보호합니다. 물리적 단위에서 데이터를 보호하는 것은 메모리 상의 데이터가 일관된 상태를 유지할 수 있도록 보호하는 것입니다. 논리적 단위에서 데이터를 보호하는 것은 논리적으로 스레드가 접근할 수 있는 데이터에 접근할 수 있도록 보장하고 접근할 수 없는 데이터는 접근할..

이전 포스팅에서 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..