05. 데이터베이스 - File Management, Index

File Management는 레코드를 쉽게 찾을 수 있도록, 데이터베이스의 테이블을 페이지로 나누어서 관리합니다.

Index Management 라고 부르기도 하는데, Index는 이후에 다시 설명하겠습니다.

그리고 해당 레이어에서 중요한 것은 파일에 페이지를 어떻게 구성하여 관리할 지를 정하는 것입니다.

 

앞선 글에서도 나왔듯이 파일에 페이지를 구성하는 여러 방법이 존재하고, Heap File, Sorted File, Index File 방법에 대해 다루었습니다. 

여기서 무조건적으로 좋은 파일 구조는 없으며, 상황에 따라 좋은 방식을 잘 선택하는 것이 중요합니다.

우선 Heap File로 데이터베이스를 구성하면,

예를 들어, Heap File은 레코드를 순서없이 그냥 모아둔 것이므로 모든 레코드를 순회하는 연산이 많이 일어나는 경우 적합합니다.

Sorted File의 경우에는 검색을 쉽게 할 수 있으며, 특정 범위의 레코드를 찾는 경우 적합합니다.

 

위의 두 방식으로 데이터베이스를 구성하면  Page number와 페이지내에서 레코드의 위치 (offset)을 통해 레코드를 쉽게 찾을 수 있습니다. 하지만 테이블의 Column 값 (혹은 레코드자체가 갖는 특정한 key 값)들을 이용하여 레코드를 찾을 때는 효율적으로 검색할 수 없습니다. 

Index를 이용하면 이 문제를 효율적으로 해결할 수 있습니다.

 

Index

Index : Search Key를 기준으로 원하는 데이터를 빠르게 찾을 수 있도록 하는 자료구조

여기서 Search Key란 Relation에 존재하는 Attribute들의 부분집합이며, Unique할 필요는 없습니다.

Index에는 B+ Tree, Hash table 등이 있으며, 해당 글에서는 B+ Tree에 대해 살펴보겠습니다. 

 

B+ Tree

B+ Tree는 B-Tree를 개선한 자료구조이고, 

B-Tree는 각 노드가 여러 개의 자식을 가질 수 있도록 이진탐색트리를 확장시킨 m-way Search Tree의 일종입니다.

B-Tree에 대한 자세한 설명은 아래 게시물에서 볼 수 있습니다.

10. 자료구조론 - B-Tree

이진트리는 자식이 많아봐야 두개밖에 없기때문에 탐색 등의 연산을 빠르게 수행할 수 있습니다.

하지만 이진트리는 데이터베이스와 같이 디스크에 데이터를 저장하는 용도로 사용하기에는 적합하지 않은 자료구조입니다. 

모든 데이터가 메인메모리에 들어있을 수는 없기 때문에 일부 데이터는 외부 디스크에 저장됩니다. 이때 디스크에 접근하는 것은 메인메모리에 접근하는 것보다 훨씬 느립니다. 

그리고 디스크는 여러 개의 구역 (blocks, pages) 으로 나뉘어 있고, 구역 내의 특정 부분을 접근하는 것과 해당 block 전체를 접근하는 것은 동일한 시간이 걸립니다. 

따라서 디스크에서 데이터를 가져올 때 시간을 줄이기 위해서는 디스크에 한번 접근해서 가져오는 데이터의 양을 늘리고, 디스크에 접근하는 횟수를 줄여야합니다. 즉 트리의 각 노드를 좀 더 넓게 만들어야합니다.

이렇게 넓어진 노드에 대한 데이터를 한 번에 가져오고나면 그 안에서 원하는 레코드를 찾는 것은 메인메모리에서 이진탐색 등의 방법으로 빠르게 수행할 수 있습니다.

ISAM (Indexed Sequential Access Method )

B-Tree, B+ Tree에서는 레코드의 삽입, 삭제가 발생하면 트리의 구조를 조정하는 과정을 거치도록 구성되어있습니다. 그런데 만약 어떤 데이터베이스가 한번 만들어지고나면 그 이후에 Modification (Insert, Delete등에 의해 트리의 구조가 바뀌는 것)은 거의 일어나지 않는다면, B+ Tree보다는 ISAM 구조를 사용하는 것이 더 좋습니다.

 

ISAM 은 초기 IBM 컴퓨터를 위해 개발된 Static한 Index로, 인접한 데이터는 물리적으로도 디스크에 연속적으로 저장됩니다. 

따라서 Insert, delete에 의해 트리 구조에 조정이 일어나게되면, 디스크 내에서도 레코드의 위치를 옮겨야하는데 이는 너무 큰 오버헤드가 됩니다. 그래서 ISAM에서는 트리 구조를 변경하는 대신, 맨 뒤에 Overflow page를 따로 만들어 중간에 들어갈 수 없는 값들을 따로 모아둡니다. ISAM구조의 장점은 레코드들이 physical하게 연속적으로 저장되어 있다는 점인데, 이렇게 Overflow page에 들어간 레코드들은 이런 장점을 가질 수 없게됩니다.

따라서 ISAM 구조는 데이터베이스에 많은 Modification이 발생하지 않을 것이라 예상되는 경우 사용하는 것이 좋습니다.

 

B+ Tree

B+ Tree는 dynamic한 상황에서 ISAM에 발생했던 문제를 효율적으로 해결합니다.

B-Tree에서는 모든 노드에 데이터를 저장했던 것과 달리 B+ Tree에서는 리프노드에만 데이터를 저장합니다. 그리고 Internal 노드에는 <key, 자식노드에 대한 포인터> 가 들어갑니다. 

또 모든 리프노드는 링크드리스트 형태로 연결되어 페이지들이 메모리에 순서대로 저장되어있지 않더라도 편리하게 데이터를 순차적으로 순회할 수 있습니다.

또 Internal node에는 데이터가 저장되지 않아 용량이 적어서 하나의 Disk Block에 더 많은 Internal node를 자식으로 넣을 수 있습니다. 따라서 B-Tree에 비해 더 적은 수의 Disk Block에 접근하여 원하는 페이지를 찾을 수 있게됩니다.

 

B+ Tree에서 검색 연산의  Complexity를 간단히 살펴보면, $O(log_M(B))$ 가 됩니다. 여기서 M은 들어갈 수 있는 자식 노드의 개수이며, B는 총 페이지의 개수로 $log_M(B)$ 는 B+ Tree의 높이로 볼 수 있습니다. 

만약 페이지의 크기가 16KB이고 key와 자식노드에 대한 포인터가 각각 8바이트로 한 쌍이 총 16바이트이면, 한 페이지에는 1024개의 쌍이 들어갈 수 있습니다. 그러면 M은 1024가 되고, 이 정도 트리에서는 트리의 총 높이가 3~5 정도만 되어도 꽤 큰 용량의 데이터를 처리할 수 있습니다. 트리의 총 높이가 3~5라는 것은, 3~5번의 디스크 접근이면 원하는 레코드를 찾을 수 있다는 뜻이므로 매우 빠름을 알 수 있습니다.

 

또한 자동으로 트리의 Balance를 맞추어 어떤 레코드를 탐색하든 거의 균등한 탐색시간이 보장됩니다.

B+ Tree는 AVL Tree 와 달리 Leaf 를 추가하여 트리를 조정하는 대신 Leaf 를 쪼갠 후 새로운 부모노드를 만들어 계속 위로 올려보내는 방식으로 동작합니다. 

 

(B+ Tree의 알고리즘에 대한 자세한 내용은  http://www.amittai.com/prose/bpt.c 의 코드를 참고)

 

 

여기서 Delete가 일어날 때, Delayed Merge를 적용할 수 있습니다.

B+ Tree 에서는 한 page에서 최소로 가져야하는 key의 개수가 있습니다. 따라서 Tree에서 key를 delete한 뒤, 해당 page의 key의 개수가 이보다 작아지게 되면 이웃한 페이지에서 entry를 가져오는 redistribute 혹은 이웃한 페이지와 합치는 merge를 수행하게 됩니다.

그런데 이렇게 기준을 엄격하게 잡게되면, 한 두개씩 key가 계속 지워졌다 들어왔다 하는 상황에서 반복적으로 merge, split이 발생하는 문제가 생길 수 있습니다. 

그런데 이러한 Redistribute나 Merge같이 B+ Tree의 구조를 바꾸는 structure modification의 경우, 많은 양의 Disk I/O가 발생할 수 있습니다. Disk에 접근하는 것은 memory내에서의 작업에 비해 시간이 오래걸리기 때문에, 이렇게 되면 데이터베이스의 성능이 저하됩니다.

따라서 이를 개선하기 위한 방법으로 page가 가져야 하는 최소 key 개수의 제한을 완화시켜 structure modification의 횟수를 줄이는 Delayed Merge를 적용할 수 있습니다.

 

Bulk Loading B+ Tree

Bulk Loading은 DB를 새로 생성하거나, 옮기는 것과 같이 많은 양의 데이터셋에 대해 Index를 생성할 때 사용할 수 있는 방법입니다. 

엄청나게 큰 테이블에 대해 B+ Tree를 생성하고자 할 때, 개별 레코드에 대해 반복적으로 Insert를 호출한다면 어떨까요?

레코드가 들어갈 위치를 루트노드부터 시작하여 반복적으로 찾아야하고, 랜덤한 페이지를 끊임없이 수정하여 캐시 효율이 낮아져 매우 느리게 동작합니다.

 

벌크로딩은 다음과 같이 동작합니다.

1. 우선 데이터를 모두 입력받아 key를 기준으로 정렬합니다.

2. 특정 fill factor 까지 leaf page를 채웁니다.

3. parent 페이지가 꽉차게 되면 parent page를 split합니다.

• 이때 split되는 기존 노드와 새로 생긴 노드의 occupancy invariant를 맞추기 위해 절반씩 나눌 필요 없이 기존 노드는 fill factor만큼의 item은 가지고있도록 split을 진행합니다.
• 이는 bulk loading이라는 특수한 상황을 고려하여 이후에도 많은 양의 데이터가 들어올 것임을 알고있기 때문에 occupancy invariant 를 완화하여 효율을 높이는 것입니다. 

이렇게 Index를 생성하게 되면, 반복적으로 루트노드부터 원하는 노드를 찾을 필요가 없기 때문에 더 적은 Disk I/O가 필요하고, Leaf 노드들은 순차적으로 저장되게 됩니다. 또한 각 페이지에 원하는 fill factor를 적용할 수도 있습니다. 

 

Storing Data Entries

인덱스에서 실제 데이터가 Leaf 노드에 저장되는 방식에 대해 살펴보겠습니다. 

 

1. 실제 레코드 값을 직접 집어넣는 방식 (by Value)

인덱스에 실제 튜플 값이 바로 들어가기 때문에, 인덱스에서 leaf 노드를 찾은 이후 레코드를 얻기 위해 포인터를 거칠 필요가 없습니다. 

 

2. 매칭되는 데이터에 대한 record id를 레퍼런스로서 집어넣는 방식 (by Reference)

인덱스에 레코드 값을 직접 넣는 대신 rid를 통해 레코드를 찾아갈 수 있도록 합니다.

따라서 인덱스의 리프노드에는 <key, 매칭되는 레코드의 rid> 가 들어가게 됩니다. 

그런데 key가 Unique하지 않을 때, 하나의 key에 대해 매칭되는 rid가 여러 개 있을 수 있습니다.

 

3. 매칭되는 데이터에 대한 모든 rid를 리스트로 집어넣는 방식 (by List of references)

위의 문제를 해결하기 위해 key에 대해 중복되는 rid들을 리스트로 한 번에 저장하는 방식이 있습니다.

따라서 인덱스의 리프노드에는 <key, List of rid>가 들어갑니다.

 

만약 하나의 테이블에 대해 여러 종류의 인덱스를 만들고자한다면 2번과 3번 방식을 사용하는 것이 좋습니다.

왜냐하면 2번과 3번은 실제 레코드 값은 따로 저장되어 있고, 인덱스에는 reference만이 저장되어 있기 때문에 실제 레코드 값을 여러 인덱스에서 함께 사용할 수 있기 때문입니다. 

(1번 방식으로도 이를 구현할 수는 있지만 비효율적일듯)

 

Clustered & Unclustered Index

1. Clustered Index

Index의 노드 내 레코드들이 실제 데이터가 physical하게 저장된 순서대로 저장되어 있는 Index입니다.

즉, 인덱스의 구조가 데이터 행이 정렬된 순서대로 저장되는 것입니다. 따라서 Clustered Index는 한 테이블에 하나씩만 존재할 수 있습니다.

이렇게 정렬된 Index는 해당하는 key값을 기준으로 검색 시 성능적으로 이점을 얻을 수 있습니다.

또한 특정 범위의 레코드를 검색할 때 locality의 이점을 얻을 수 있습니다. 

2. Unclustered Index 

Index 내 레코드들의 logical한 순서가 physical한 순서와 상관없이 저장되어있는 Index입니다. 

3. Primary Index vs Secondary Index

Primary Index는 primary key를 기준으로 인덱스를 정렬한 것입니다. 이렇게  만들어진 인덱스는 보통 clustered Index가 됩니다.

만약 primary key가 아닌 다른 Column들에 대해 쿼리가 많이 작성된다면, 다른 key를 통해 정렬된 Index를 만드는게 더 성능을 높일 수 있습니다. 이렇게 빌드된 Index는 secondary Index라고 하며, 일반적으로 unclustered 일 확률이 높습니다.

 

만약 Secondary Index를 너무 많이 만들어놓게된다면 레코드 위치가 변경될 때 모든 index를 찾아 rid를 변경해주어야하기 때문에 성능에 저하가 올 수 있습니다.