[見心見性] 사람중심의 IT세상을 꿈꾸는 Microsoft MVP

IL.NET 2/26/2008 12:39:42 AM

#5 인덱스 아키텍처

데이터베이스에서 인덱스(Index)는 조회 성능을 높이기 위해서뿐만 아니라 유니크나 프라이머리 키 제약과 같은 제약 조건을 구현하기 위해서도 사용된다. 따라서 데이터베이스에서 인덱스를 논외로 하고서는 데이터 저장 구조를 논할 수 없다. 게다가 데이터 페이지조차도 이러한 인덱스 아키텍처에 매우 밀접한 영향을 받는다.

인덱스 또한 데이터이므로 별도의 인덱스 페이지로 관리된다. 다만, 데이터 페이지의 경우에는 링크드 리스트 보다 정확히는 더블 링크드 리스트(Double linked list)로 관리되는 반면, 인덱스 페이지는 B-Tree(Balanced tree or Binary tree)로 관리된다. B-Tree자료구조의 특징은 마치 나무를 거꾸로 뒤집어 놓은듯한 모양의 삼각형 구조로 기본이 되는 루트 노드를 중심으로 노드들이 하위로 연결되어 있으며 어떤노드에 대한 탐색 횟수도 동일한 균형 탐색구조를 가진다는 특징을 하고 있어서, 빠른 검색을 요하는 경우에 적합하다.

아래 <그림>이 인덱스의 B-Tree 구조를 나타내고 있다. 사각형으로 박스 처리된 A에서 H까지가 각각 노드들이다. 그리고 이 노드들은 Root Node Level, Intermediate Level(중간수준), Leaf Level의 세가지 레벨 수준들을 가진다.

최상위 층이 Root Node Level이고 가장 마지막에 있는 것이 Leaf Level이다. 중간에 위치하는 여러 수준들이 Intermediate Level이다. Root Node는 위에 아무런 노드가 없는 것이고 Leaf Level Node들은 더 이상 아래에 아무런 노드들이 없다.

이러한 B-Tree의 장점은 원하는 노드를 찾는데 빠르고, 일정한 시간 내에 처리할 수 있다는 것이다. 예를 들어 H 노드가 가진 “훈스닷넷”라는 값을 찾아보자. 우선 가장 루트 노드를 검색해서 조건을 비교하게 된다. A노드에서 B, C, D 노드들과 검색어인 훈스닷넷를 비교하면 B와 C노드에는 값이 없다.

다만 “훈” 이라는 문자는 D노드의 범위에 들어가기 때문에 D노드로 포인터를 이동한다. D노드에서 다시 하위 노드들을 비교하면 H노드에 실제 원하는 값이 있는지를 찾아낼 수가 있다. D노드의 자식 노드들은 모두 정렬이 되어있기 때문에 “훈스닷넷” 라는 제목을 가지는 데이터들이 여러 개 있다면 다음 노드들을 모두 탐색해보면 된다. 기껏해야 D노드 하위의 노드들을 모두 탐색해내는 것이기 때문에 테이블 스캔과 같이 A노드에서 H노드까지 모두 검색해낼 필요가 없기 때문에 빠르게 원하는 노드로 접근할 수 있다.

참고서적:Deep Inside T-SQL

크리에이티브 커먼즈 라이센스