3. Data File & Index File

개요

이제 스토리지 엔진이 어떻게 데이터를 저장되는지 정리하기에 앞서, data file 과 index file 에 대해 정리해보려고한다.

우리는 왜 데이터를 단순히 파일 시스템이 아니라 DBMS 를 사용해서 저장할까?

 

DBMS도 데이터를 저장할 때 파일로 저장하지만, DBMS 는 파일 시스템이 제공하는 디렉토리 / 파일의 계층 구조를 사용하지 않는다.

또한 파일을 만들 때도 DBMS에서 직접 결정한 포맷에 맞춰 파일을 구성한다.

이렇게 하는 이유는 크게 3가지 이유가 있다.

 

1. Storage Efficiency

DBMS는 데이터 레코드를 저장할 때 storage overhead 를 최소화하는 방식으로 파일을 구성한다.

 

2. Access Efficiency

원하는 레코드를 찾을 때 최소한의 단계를 거쳐서 찾을 수 있다.

 

3. Update Efficiency

레코드를 수정할 때 디스크에 변경을 최소화한다.

 

---

 

데이터베이스는 data record 를 저장한다.

record 라는 이름에서 알 수 있듯, 각 레코드는 테이블 속 여러 개의 field 로 구성되어 있다.

또한 각 테이블은 하나의 분리된 file로 표현한다.

 

테이블에 있는 각각의 레코드는 search key 를 통해서 찾을 수 있다.

레코드를 찾기 위해 데이터베이스는 index 를 사용한다.

인덱스는 전체 테이블을 스캔하지 않아도 원하는 레코드를 효율적으로 찾을 수 있도록 도와주는 보조 자료구조로, 하나의 레코드를 식별할 수 있는, 레코드를 구성하는 field의 부분집합으로 만들어진다.

 

데이터베이스는 보통 data file 과 index file 을 분리해서 다룬다.

이름 그대로 data file 은 data record 를 저장하고 있는 파일이다.

index file 은 record 의 메타데이터를 저장하고 있으며, 이 데이터를 사용하여 data file 에 있는 데이터를 찾는다.

인덱스 파일은 data file 에 있는 데이터를 찾기 위한 데이터만 갖고 있기 때문에 데이터 파일보다 일반적으로 크기가 작다.

 

하나의 파일은 여러개의 페이지로 구성되어 있다.

따라서 데이터 파일도, 인덱스 파일도 여러 페이지로 구성되어 있으며, 인덱스 파일을 구성하는 페이지의 수는 데이터 파일을 구성하는 페이지의 수보다 작을 것이다.

각각의 페이지는 하나 이상의 디스크 블록으로 구성되어 있다. (디스크가 읽고 쓸 때 사용하는 기본 단위가 블록이기 때문에 당연하다)

그리고 각각의 페이지는 레코드의 나열이나 slotted page 형태로 구성되어 있다.

 

새로운 레코드를 삽입하거나, 기존 레코드를 수정하는 작업은 키-값 쌍의 형태로 표현된다.

데이터를 삭제하는 경우, 대부분의 최근 스토리지 엔진은 페이지에서 직접 데이터를 삭제하지 않고 deleteion marker (tombstone 이라고도 부름) 을 사용한다.

deletion marker 는 삭제에 대한 메타데이터(키, 타임스탬프 등)를 갖고 있다.

 

기존 레코드를 수정하거나 삭제하면 해당 레코드에는 수정, 삭제가 되었다는 표시가 남으며 (shadowed)

이렇게 표시가 남은 레코드는 가비지 콜렉션 작업을 통해 회수된다.

가비지 콜렉션은 페이지를 읽고 표시가 없는 레코드를 새로운 공간에 쓰고, 표시가 남아 있는 레코드는 버리는 작업이다.

 

Data File

데이터 파일 (또는 primary file 이라고 부르기도 한다.) 은 크게 3가지 방법으로 구현할 수 있다.

 

1. index-organized tables (IOT)

데이터 레코드를 인덱스 안에 저장한다.

레코드가 key 순서대로 저장되어 있기 때문에 범위 스캔시 IOT 방식은 순서대로 파일 content 를 스캔하는 방법으로 구현된다.

 

2. heap-organized tables (heap files)

힙 파일에 저장되는 레코드는 특정한 순서를 따르지 않아도 된다. (물론 정렬해서 저장할 수도 있다.)

이 경우, 레코드는 파일에 추가된 순서대로 저장되어 있기 때문에 새로운 페이지가 파일에 추가될 때 파일을 재구성하는 등 추가적인 작업이 필요하지 않다는 장점이 있다.

대신 힙 파일은 데이터 레코드 위치를 가리키고 있는 별도의 추가적인 인덱스 구조가 필요하다.

 

3. hash-organized tables (hashed files)

해시 파일의 경우, 레코드는 bucket 에 저장된다.

그리고 각 레코드 key 의 해시값은 이 레코드가 속한 버킷을 가리킨다.

하나의 버킷에는 여러 레코드가 저장될 수 있다.

이때 각 버킷에 저장된 레코드는 추가된 순서대로 저장될 수도 있고, 탐색 속도를 높이기 위해 특정 기준으로 정렬해서 저장할 수도 있다.

 

 

IOT 방법의 경우 디스크 조회 횟수를 최소 1번 이상 줄일 수 있다.

데이터 레코드를 찾기 위해 인덱스를 탐색하면, 그 결과로 인덱스 파일 안에서 원하는 데이터를 주소없이 바로 가져올 수 있기 때문이다. 반면 다른 방법의 경우 인덱스가 가리키고 있는 위치로 한번 더 접근해서 데이터 레코드를 읽어와야 하므로 디스크 탐색 횟수가 최소 1번 이상 추가로 필요하다.

 

만약 데이터 레코드를 인덱스와 분리하여 저장하는 경우, 인덱스 파일은 data entry 를 갖는다.

데이터 엔트리는 데이터 레코드를 유일하게 식별할 수 있으며, 데이터 파일에서 데이터 레코드를 찾을 수 있는 정보를 갖고 있다.

예를 들면 데이터 파일에서 데이터 레코드가 위치한 file offset (또는 row locator) 을 저장하거나, 해시 파일의 경우 bucket ID 를 저장할 수 있다.

IOT 방식의 경우 data entry 가 실제 data record 정보를 갖고 있다.

(그래서 디스크를 추가적으로 탐색할 필요가 없다.)

 

 

Index File

인덱스는 데이터 레코드를 효율적으로 조회하기 쉬운 방식으로 디스크의 데이터 레코드를 구성한 구조를 말한다.

인덱스 파일은 레코드를 식별할 수 있는 키와 데이터 파일 내 레코드의 위치를 매핑하는 특별한 구조로 구성되어 있다.

heap file 에서는 이 키로 레코드를 식별한다.

IOT 방식에서는 인덱스 파일에 primary key 를 저장한다.

 

데이터 파일에 대한 인덱스를 가리켜 primary index 라고 말한다.

(즉, 데이터 레코드를 직접 가리키고 있는 인덱스를 말한다.)

대부분의 경우, primary index 는 primary key 또는 PK 처럼 레코드를 식별할 수 있는 키 집합으로 구성되어 있다.

그리고 그 외의 인덱스는 secondary index 라고 부른다.

 

secondary index 는 데이터 레코드를 직접 가리킬 수도 있고, 단순히 데이터 레코드의 primary key 를 저장할 수도 있다.

데이터 레코드를 가리키는 경우, heap file 또는 IOT 방식에서 offset 정보를 갖고 있을 수 있다.

이때 여러 secondary index 가 같은 데이터 레코드를 가리킬 수 있기 때문에, 하나의 데이터 레코드는 서로 다른 필드에 의해 식별될 수도 있고, 다른 인덱스를 통해 위치를 찾을 수도 있다.

primary index file 이 search key 마다 하나의 유일한 data entry 를 갖고 있는 것과 다르게, secondary index file 은 하나의 search key 에 대해서 여러개의 entry 가 존재할 수 있다.

 

만약 데이터 레코드가 search key 순서와 동일하게 정렬되어있다면, 이 인덱스를 가리켜 cluster 되어 있다고 말한다. (clustered index)

cluster 된 데이터 레코드는 보통 인덱스와 같은 파일에 저장되어 있거나 (별개의 파일이지만) key 순서가 일정 기준으로 항상 정렬되어 있는 clustered file 에 저장되어 있다.

 

만약 데이터 파일과 인덱스 파일이 서로 분리되어 있고, 데이터 레코드의 순서와 키 순서가 다르다면, 그 인덱스를 가리켜 nonclustered 또는 unclustered 라고 부른다.

 

참고로, IOT 방식은 인덱스 안에 데이터가 들어있기 때문에 자연스럽게 인덱스 파일에 저장된 key 순서와 데이터 순서가 일치하므로 clustered index 이다.

또한 Secondary Index 는 정의상 primary key 이외의 키로 데이터 레코드에 접근하기 위해 사용되기 때문에 자연스럽게 nonclustered index 로 분류된다.

clustered index 는 index-organized 방식이 될 수도 있고, index file 과 data file 이 분리되어 있을 수 있다.

 

---

 

많은 데이터베이스는 하나의 레코드를 유일하게 식별할 수 있는 column 집합인 primary key 를 갖고 있다.

만약 primary key 가 명시되지 않은 경우, 스토리지 엔진은 암시적인 primary key 를 생성할 수 있다.

예를 들어 MySQL InnoDB 스토리지 엔진의 경우, 자동으로 auto-increment column 을 추가한다.

 

primary key 개념은 관계형 DB, dynamo-based NoSQL 저장소, document 저장소 등 여러 종류의 DBMS 에서 사용된다.

이 개념을 지칭하는 이름은 DBMS 마다 다를 수 있지만, 대부분 primary key 에 대응하는 개념이 존재한다.

 

Primary Index 를 간접 참조하기

데이터 레코드가 인덱스에 의해 직접 참조되어야 하는지 (file offset 등으로) 아니면 primary key index 를 거쳐서 간접 참조되어야 하는지에 대해서는 데이터베이스 커뮤니티에서도 의견이 분분하다.

 

이 두 방법 모두 자단점이 장단점이 있다.

데이터를 직접 참조하는 경우, 디스크 탐색 시간을 줄일 수 있지만, 데이터가 수정되거나, 위치가 바뀌는 경우 포인터를 업데이트하는 비용이 발생한다는 단점이 있다.

반면 primary index 를 간접적인 방식으로 사용하면 포인터를 업데이트하는 비용이 줄지만, 데이터를 조회할 때 비용이 더 많이 발생한다.

만약 워크로드가 대부분 조회 연산으로 구성되어 있다면, 데이터를 직접 참조하여 몇 개의 인덱스를 수정하는 것이 더 효과적일 것이고, 여러 인덱스가 존재하며 쓰기 연산이 많은 경우에는 데이터를 간접 참조하여 포인터 수정을 최소화하는 것이 더 좋을 것이다.

 

예를 들어 MySQL InnoDB 는 primary index 를 사용하며, 쿼리를 실행할 때 primary index, secondary index 에서 각각 한번씩 두번의 조회를 실행한다. secondary index 로 레코드를 찾고, 각 레코드의 실제 저장 위치를 primary index 를 통해 찾는 것이다.

이 방식은 secondary index 에서 직접 offset 을 따라가는 대신, primary index 를 조회하는 오버헤드가 추가된다.

 

또는 이 두 방식을 섞어서 data file offset 과 primary key 를 모두 저장하는 방법도 사용할 수 있다.

먼저 data offset 을 체크하고, 이 값이 여전히 유효하다면 offset 을 따라 바로 찾아가면 되고, 만약 변경에 의해 이 값이 유효하지 않다면 primary key 를 통해서 추가적인 비용을 지불하고 데이터를 찾은 뒤, 새로운 offset 값으로 index file 을 수정한다.