[데이터베이스] ISAM과 B+ 트리

ISAM(Indexed Sequential Access Method)

ISAM은 트리의 구조가 변경되지 않는 정적 트리이다. 리프 페이지는 연속적으로 할당되어 앞, 뒤의 링크 없이 순차적으로 접근이 가능하다는 점이 특징이자 장점이다. 데이터 삽입 시 overflow page가 생성될 수 있으며 order 개념이 없다.

 

특징

• 레코드가 물리적으로 인접해있다.
• 트리 구조가 변경되지 않는다.
• 인덱스 레벨의 페이지가 변경되지 않으므로 병행성 제어가 쉽다.

 

ISAM의 삽입과 삭제

좌측은 23,48,41,42를 삽입한 뒤의 모습이고, 우측은 42,51,97을 삭제한 뒤의 모습이다.

---

B+ 트리

동적인 트리로 데이터의 삽입, 삭제에 의해 트리의 구조가 변경될 수 있다. 리프 페이지의 노드들은 앞, 뒤 링크로 연결되어 있으며 높이 균형을 유지한다.

 

특징

• 삽입과 삭제로 인해 트리 구조가 바뀔 수 있다.
• 루트를 제외한 각 노드는 d≤m≤2d의 점유율을 만족해야 한다.

order(d)=2인 B+트리

B+ 트리의 삽입

리프 노드가 2d일 경우 리프 노드에서는 노드가 두개로 나뉘어지는 split이 발생하고 중간 값이 상위 노드로 복사되는 copy up이 발생한다. 점유 조건을 만족하는 경우에는 단순히 삽입이 이루어진다.

8*의 삽입 결과

위는 8*의 삽입 결과로 가장 좌측 노드가 split된 뒤 중간값인 5가 copy up 되고, 상위 노드 또한 공간이 부족해 split과 copy up이 연쇄적으로 발생했다.

 

 

B+ 트리의 삭제

삭제 후 노드의 점유율이 d 이상일 경우 문제가 없으나, d 미만일 경우 아래와 같은 구조 변경 작업이 이루어진다.

• sibling의 노드가 d+1 이상으로 여유있을 경우: sibling에서 키 값을 가져오는 re-distribution이 이루어지고 부모의 노드가 변화된다.
• sibling의 노드가 d 이하일 경우: sibling과 병합 후 인덱스 노드에서 필요 없는 키 값이  없어지는 toss가 발생한다.
  • 만약, toss 이후 인덱스 노드가 점유 조건을 만족하지 않을 경우 아래와 같이 처리한다.
    
    • sibling의 노드가 d+1 이상인 경우: push through로 re-distribution
    • sibling의 노드가 d 이하일 경우: pull down으로 병합

아래는 19*, 20*을 순서대로 삭제한 뒤의 구조이다.

초기 19*를 삭제할 때는 삭제 후에도 점유 조건을 유지하여 특별한 구조 변경이 이루어지지 않았다. 이후 20*을 삭제할 때 우측 sibling이 d+1이었으므로 24*를 우측 노드에서 가져오는 re-distribution이 발생하고, 인덱스 노드의 24*가 27*로 변경되었다.

 

 

아래는 24*를 삭제한 뒤의 구조이다.

24*가 삭제되면 점유 조건을 만족하지 않아 조정이 필요하고, 우측 silbing이 d 이하이므로 [22,x,x,x]와 [27,29,x,x]가 병합되어 [22,27,29,x]로 변경되고 인덱스 노드의 27*이 더 이상 필요가 없어져서 toss가 발생한다.

 

위 작업 이후 인덱스 노드 [30,x,x,x]가 되어 점유 조건을 만족하지 않게 되고, 좌측 sibling이 d 이하이므로 더 상위 노드인 루트의 pull down을 통해 [5,13,x,x], [17,x,x,x], [30,x,x,x]가 병합된다.

 

 

좌측 인덱스 노드가 여유로운 상황에서 24*가 삭제될 경우

위는 좌측 sibling의 인덱스 노드가 d+1 이상으로 여유로운 상황이고, 현재 24*가 삭제되고 인덱스 노드의 27*이 삭제된 뒤 [30*,x,x,x]가 되어 점유 조건을 만족하지 않는 상황이다.

 

위의 경우 sibling에서 push-through를 통한 re-distribution이 가능하다. 루트 노드의 22*가 우측 노드로 내려오고 좌측 인덱스 노드의 20*이 루트로 올라간다. 이후, 다시 루트에 존재하는 20*이 우측 인덱스 노드로 내려오고 17*이 루트로 올라가며 조정된다.

사실 루트 노드의 22*가 우측 노드로 내려오고 좌측 인덱스 노드의 20*이 루트로 올라가는 작업만 이루어져도 문제 없지만, 학습한 교재에서는 좌측노드는 2개, 우측노드는 3개의 키 값을 가지도록 되어있다.

최종적인 트리 상태

 

Prefix Key Compression

긴 문자열과 같은 필드를 인덱스의 검색 키로 사용할 경우 구분되는(distinct) 앞의 일부 데이터만 검색 키로 활용하여 인덱스 노드에 존재할 수 있는 키의 수(fan-out)를 늘어나 이에 따라 키의 높이가 줄어들어 검색이 빨라지게 하는 기법이다.

 

 

Bulk-loading

많은 양의 데이터를 삽입할 시 해당 값들을 검색키를 기반으로 정렬한 뒤 순서대로 삽입하여 트리 구조의 변화가 우측 패스에만 발생하게 하여 단순 삽입에 비해 효율적이며 리프 노드가 순차적으로 저장된다.