[파일구조] - Virtual B 트리

1. 개요

B 트리 구조를 이용하여 인덱스를 저장한 데이터 파일을 읽기 위해서는 항상 B 트리의 root node가 저장된 페이지를 하드디스크에서 읽어야 한다. 그러나 하드디스크에서 데이터를 읽는 것은 막대한 비용이 소모되기 때문에 파일 시스템의 성능을 저하시키는 요인으로 작용한다.

이러한 문제를 해결하기 위해 B 트리의 root node가 저장된 페이지를 메모리에 유지하는 keep-the-root strategy가 고안되었다. Virtual B 트리는 keep-the-root-strategy를 확장하여 B 트리를 구성하는 정보가 저장된 몇 개의 페이지를 메모리 상의 버퍼에 저장하여 하디드스크 접근을 최소화하는 B 트리의 변형이다.

2. Page Replacement 알고리즘

Virtual B 트리는 제한적인 크기의 버퍼를 이용하여 페이지를 메모리에 저장하기 때문에 더 이상 버퍼에 페이지를 저장할 수 없는 경우가 발생하는데, 이러한 경우에는 새로운 페이지를 버퍼에 저장하기 위해 기존의 페이지를 제거해야한다.

1) LRU(Least Recently Used) replacement

LRU replacement는 단어 그대로 최근에 가장 적게 사용된 페이지를 버퍼에서 제거하는 정책이다. B 트리의 insert, remove 등의 연산에서는 반복적 또는 재귀적으로 특정 노드 그룹을 계속해서 참조하는 경우가 빈번하게 발생한다. Virtual B 트리의 LRU replacement 정책은 이러한 B 트리의 특성을 고려한 것이다.

2) Height-based replacement

B 트리의 많은 연산들은 주어진 key 값에 해당하는 leaf node를 찾는 작업에서부터 시작된다. 주어진 key 값에 해당하는 leaf node를 찾을 때는 반드시 root node에서부터 시작하여 점점 높이가 낮아지는 방향으로 탐색을 진행한다. 따라서, 아래의 그림과 같이 높은 층에 위치한 노드는 낮은 층에 위치한 노드보다 더 빈번하게 참조될 가능성이 높다.

Height-based replacement 정책은 B 트리의 이러한 속성을 고려하여 가능하면 높은 층에 위치한 노드에 대한 페이지를 버퍼에 오래 유지하는 것이다.