[데이터베이스] 18. 파일과 인덱스 (레코드 저장 방법)

파일

DBMS가 데이터를 다룰 때는 '파일(file)' 로 추상화하여 다룬다.

파일은 레코드들의 집합이며, 하나 이상의 페이지로 구성되어 있다.

그림으로 보면 이해가 쉽다.

 

 

DBMS가 다루는 파일은 여러 개의 레코드로 이루어져있다.

(이 레코드는 테이블에 저장되는 하나의 데이터 레코드와 비슷한 의미로 이해했다.)

 

이때 파일은 여러 레코드를 가지는 페이지로 나누어진다.

메모리에 적재되어 실행중인 DBMS 프로그램이, 디스크에 저장된 레코드를 메모리로 읽어오거나, 처리한 레코드를 디스크에 쓸 때는 항상 페이지 단위로 주고 받는다.

데이터베이스에서 읽어오는 페이지는 1KB ~ 8KB 까지 다양한 크기가 존재할 수 있는데, 페이지의 크기는 보통 4KB 또는 8KB 이다.

 

레코드에는 그 레코드를 식별할 수 있는 레코드 ID(rid)가 존재하며, 이 값을 통해 이 레코드를 포함하고 있는 파일이 디스크 어디에 있는지 디스크 주소를 식별할 수 있다.

 

위 그림은 하나의 파일이 4개의 페이지 (파란 사각형) 으로 구성되어 있고, 각각의 페이지는 3개의 레코드로 구성되어 있음을 알 수 있다.

결론적으로 이 파일은 3x4 = 12개의 레코드로 구성된 파일임을 알 수 있다.

 

이때 하나의 파일 안에 레코드를 배치하는 방법은 여러가지가 있다.

각 방법마다 파일 내에서 레코드와 관련된 연산을 수행할 때 어떤 연산은 효율적이고, 어떤 연산은 비효율적인 특징이 있다.

레코드와 관련된 연산으로는 모든 레코드를 조회하는 스캔, 등호 조건 조회, 범위 조건 조회, 레코드 삽입, 레코드 삭제가 있다.

파일 안에 레코드를 배치하는 방법 별 각 연산의 효율 비교는 후술한다.

 

 

힙 파일

힙 파일은 레코드를 제일 단순하게 저장하는 파일 구조로, (자료구조 힙과는 관련이 없다)

레코드를 저장할 때는 레코드가 들어온 순서에 맞춰 차곡차곡 파일에 저장한다.

힙 파일로 데이터를 저장했을 때, DBMS에서 레코드와 관련된 연산의 수행 시간을 계산해보자.

 

- 스캔

하나의 파일 안에 존재하는 모든 레코드를 조회한다.

만약 하나의 파일이 F개의 페이지로 구성되어있었다면, 디스크로부터 F번 페이지를 가져와서 해당 페이지 안에 있는 모든 레코드를 스캔하면 된다.

 

- 등호 조건 조회

특정 조건에 정확히 일치하는 데이터를 탐색하려고 하는 경우, 두 가지 경우가 존재할 수 있다.

 

1. 해당 조건에 정확히 일치하는 데이터가 유일한 경우 (후보키에 대한 등호 조건)

2. 해당 조건에 정확히 일치하는 데이터가 여러개 있는 경우 (일반 필드에 대한 등호 조건)

 

책에서는 1번의 경우, 평균적으로 전체 페이지 중 절반을 탐색하면 된다고 하지만, 최악의 경우를 고려하면 두 경우 모두 디스크로부터 모든 페이지를 다 불러온 뒤, 각 페이지에 들어있는 모든 레코드를 스캔해야 한다.

 

- 범위 조건 조회

범위 조건에 일치하는 데이터가 모든 페이지에 산재해서 존재할 수 있으므로 모든 페이지를 다 불러오고, 각 페이지의 모든 레코드를 스캔해야 한다.

 

- 레코드 삽입

레코드를 삽입할 때는 힙 파일의 끝에 삽입하면 된다.

레코드 삽은 정확히 다음의 과정을 거친다.

 

1. 레코드를 삽입할 페이지를 디스크에서 읽어오기

2. 해당 페이지 맨 뒤에 레코드 삽입하기

3. 레코드를 삽입한 페이지를 디스크에 저장하기

 

따라서 페이지 관점에서는 디스크에서 로드하는 연산 한 번, 저장하는 연산을 한 번 수행한다.

디스크에 페이지를 읽고 쓰는 비용이 D라면, 레코드 삽입 연산은 2D의 비용이 소모된다.

 

- 레코드 삭제

레코드를 삭제할 때, 삭제하려는 레코드를 먼저 탐색해야 한다.

범위 조건 탐색, 동등 조건 탐색 모두 전체 페이지를 탐색해야 하고, 각 페이지에서 레코드를 찾은 뒤에는 그 페이지에서 레코드를 지우고 해당 페이지를 다시 저장해야 한다. 하나의 레코드를 삭제하는 경우, 그 레코드가 존재하는 페이지를 찾는데 F개의 페이지를 찾고, 데이터를 삭제한 뒤에 해당 페이지를 다시 저장해야 하므로 FD + D 의 비용이 들 것이다.

 

원래 데이터를 삭제한 이후에 그 자리는 구멍처럼 뚫려있으므로, 뒤의 데이터를 앞으로 한 칸씩 옮기는 작업을 해야한다.

경우에 따라서는 이런 비용을 줄이기 위해 fill factor 라고 해서, 중간에 비어있는 저장 공간을 두기도 한다.

 

정리해보면 힙 파일은 데이터를 저장하는 것은 빠르지만 조회, 수정, 삭제 시 많은 비용이 발생한다.

(레코드 수정 = 수정할 레코드 조회 비용 + 해당 페이지 저장 비용으로 생각할 수 있다)

따라서 힙 파일 방식은 레코드를 저장하기만 하고 조회, 수정, 삭제가 잘 일어나지 않는 경우에 유용하다. 

 

 

정렬된 힙 파일

파일에 레코드를 저장할 때 특정 기준에 맞추어 정렬을 유지하는 상태로 저장하는 방법이다.

(기준이 같다면 그때는 힙 파일처럼 먼저 온 것부터 순차적으로 저장된다.)

 

- 스캔

모든 레코드를 읽을 때는 그냥 힙 파일과 마찬가지로 모든 페이지를 흝어야 한다.

 

- 동등 조건 조회

특정 조건에 일치하는 레코드를 찾을 때는, 레코드가 정렬되어 있으므로 페이지 역시 정렬되어 있다.

따라서 중간 페이지를 집고, 그 안에서 내가 찾는 레코드가 존재하는지 다시 이분탐색으로 찾는 방법을 통해 레코드를 찾을 수 있다.

따라서 전체 F개의 페이지가 있을 때, 최대 log₂ F 번 페이지를 불러온다.

 

만약 동등 조건에 해당하는 레코드가 여러개 있다면, 최초 레코드를 log₂ F 에 찾고, 그 레코드부터 시작해서 같은 조건에 해당하는 레코드가 존재하는 한 다음 레코드를 계속해서 읽어나가면 여러 데이터를 불러올 수 있다.

(이 과정에서 같은 조건에 해당하는 레코드가 페이지를 넘어가면 다음 페이지를 불러오는 비용이 추가적으로 발생할 수 있을 것이다.)

 

- 범위 조건 조회

범위의 시작점에 대해 동등 조건 조회와 마찬가지로 이분탐색을 통해 찾은 뒤, 범위 안에 존재하는 한 레코드를 계속해서 읽어들인다.

 

- 레코드 삽입

먼저 레코드를 삽입할 페이지를 이분탐색을 통해 찾는다.

그리고 페이지 안에서 레코드를 삽입할 위치를 이분탐색으로 찾은 뒤, 그 위치를 비우기 위해 나머지 레코드를 모두 뒤로 밀고 비워진 위치에 삽입할 레코드를 추가한다.

 

이 뒤로 밀어내는 과정 때문에 정렬된 힙 파일은 삽입 시간이 오래 걸린다. (최악의 경우 log₂ F + F)

그래서 데이터를 뜨문뜨문 저장하는 fill factor 방식을 적용하여 데이터를 뒤로 미는 연산이 발생하는 횟수를 줄이려는 아이디어도 있다.

또는 신규 레코드가 삽입될 때 그 자리가 부족하다면 새로운 페이지를 만들어 저장하고 그 페이지를 기존에 저장하려던 페이지와 연결하는 chain page 방법을 쓰기도 한다. 이 방법을 사용하는 경우에는 chain page를 모두 탐색해야 하므로 데이터를 탐색하는데 시간이 오래 걸리는 단점이 있다.

 

레코드의 변경이 발생하여 최종적으로 데이터를 저장할 때는 반드시 '페이지 단위'로 데이터가 저장된다.

레코드가 밀려서 새로운 페이지가 생긴 경우, 그 레코드에 데이터가 하나만 존재해도 그 페이지 단위로 디스크에 저장된다.

 

이때 페이지 크기를 어떻게 잡느냐에 따라 성능이 달라질 수 있다.

페이지를 너무 작게 잡으면 필요한 데이터를 가져올 때 많은 페이지를 자주 가져와야 하고,

페이지를 너무 크게 잡아도 하나의 페이지를 가져오는 트랜스퍼 타임이 증가하므로 좋지 않다.

 

어떤 방식으로 저장하도록 할 지 결정할 때는 DBMS 벤치마킹 등을 사용하여 이 시스템이 삽입이 많은지, 조회가 많은지 등을 분석하여 적절한 종류의 데이터 저장 방식을 채택하면 된다.

 

- 레코드 삭제

삭제할 레코드를 이분탐색으로 찾고, 레코드를 삭제한 뒤, 해당 페이지를 다시 디스크에 쓰면 된다.

정렬된 힙 파일에서는 힙 파일과 다르게 삭제한 빈 공간을 관리할 수 있는 방법이 없으므로 모든 레코드를 당겨야 한다.

(페이지 내에서 이분 탐색으로 레코드를 찾을 때 빈 공간을 찝었다면 왼쪽, 오른쪽을 판단할 방법이 없다.

-> 근데 왜 위에서 '삽입' 과정에 대해서는 fill factor를 고려할 수 있다고 했을까?

책에서는 '삭제할 때는 당겨야 한다. 삽입할 때는 fill factor가 존재하지 않는다고 가정한다. 라고 했다.')

 

 

인덱스

특정 필드에 대한 검색 연산을 최적화하기 위해 데이터 레코드의 정렬 정보 데이터

이때 검색 연산을 최적화하는 '특정 필드' 를 '탐색 키(search key)' 라고 한다.

search key는 레코드를 찾는 기준 어트리뷰트이며, 꼭 하나의 튜플을 유일하게 식별할 필요는 없다.

 

인덱스의 탐색 키는 여러 필드를 포함할 수 있다.

이렇게 여러 필드로 구성된 탐색 키를 '복합 키' 라고 한다.

 

 

위 그림과 같은 테이블을 생각해보자.

만약 age 라는 하나의 search key 를 둔 경우에는 11, 12, 12, 13 순으로 인덱스가 정렬되어 가리킬 것이고,

<sal, age> 라는 복합키를 둔 경우에는 (10, 12) (20, 12) (75, 13) (80, 11) 순으로 가리킨다.

<age, sal> 라는 복합키를 둔 경우에는 (11, 80) (12, 10) (12, 20) (13, 75) 순으로 가리킨다.

 

이제 이렇게 인덱스가 주어진 상태에서 다음의 쿼리를 실행해보자.

 

 

 

만약 위와 같은 쿼리를 실행한다면 <sal, dno> 라는 복합키와 <dno, sal> 라는 복합키가 주어졌을 때, 어떤 것이 더 효율적일까?

정답은 <dno, sal> 이라는 복합키이다.

왜냐하면 일단 sal = 10000 으로 조건을 걸고 나서, 그 안에서 dno 으로 묶고 있기 때문에 sal 가 먼저 활용되며, dno 은 그 안에서 정렬될 필요가 없으므로 인덱스가 꼭 필요하지 않다.

 

 

인덱스 역시 '파일'로 저장되는데, 인덱스 파일에 들어있는 레코드를 가리켜 '인덱스 엔트리(데이터 엔트리)' 라고 한다.

하나의 파일 안에 인덱스와 실제 데이터를 함께 저장할 수도 있고(intergrated), 분리해서 저장할 수도 있다. (secondary)

보통은 인덱스와 데이터를 분리하여 저장하는 것이 좋다.

인덱스는 어지간한 경우 메모리에 다 올라오지만, 데이터는 양이 많으니 메모리에 다 올라오지 않기 때문이다.

 

데이터 엔트리는 크게 3가지 형태를 가질 수 있다.

 

1. 탐색 키를 포함하는 실제 데이터 레코드

2. 탐색 키와 rid 쌍

3. 탐색 키와 rid 리스트 쌍

 

1번과 같이 저장하는 경우를 '인덱스 파일 구성' 이라고 부르며, 정렬 파일, 힙 파일 대신에 이 방식 자체로 데이터를 저장할 수 있다.

인덱스는 그 인덱스가 가리키는 데이터의 저장 형태에 따라 군집 인덱스와 비군집 인덱스로 나뉜다.

 

군집 인덱스

인덱스는 기본적으로 정렬되어 있는 데이터이다.

인덱스의 정렬 상태와 실제 데이터의 search key 가 똑같이 정렬되어 있는 형태를 군집 인덱스라고 한다.

 

비군집 인덱스

비군집 인덱스도 인덱스는 정렬되어 있지만, 실제 데이터의 search key 가 인덱스의 정렬과 상관없이 저장된 상태를 말한다.

 

 

---

연습 문제

어떤 데이터 파일이 1만개의 페이지로 구성되어 있다.

그리고 각 페이지당 최대 20개의 튜플을 저장할 수 있다고 해보자.

 

만약 우리가 조회하려는 튜플의 개수가 '특정 범위의 100개 튜플' 일 때, (예를 들면 나이가 10 ~ 34인 사람)

과연 각 방식은 몇 개의 페이지를 디스크에서 메모리로 전송해야 하는지 비교해보자.

 

먼저 테이블에서 100 개의 튜플을 조회할 때, 각 테이블의 데이터는 디스크의 블록에 저장되어 있다.

디스크의 블록 단위로 메모리에 로딩한 뒤에는 메모리에서 페이지 단위로 데이터를 읽어온다.

 

이때 인덱스는 자신이 가리키는 데이터가 어느 블록에 있는지 알고 있다.

페이지들은 디스크든 파일이든 메모리든 이미 올라온 상태라고 해보자.

 

DBMS가 튜플을 조회하기 위해서 메모리로부터 가져와야 하는 페이지는 몇 개 일까?

 

힙 파일 : 10000 개의 페이지를 모두 찾아봐야 한다. 조건에 맞는 데이터가 어떤 페이지에 들어있을 지 알 수 없기 때문이다.

 

정렬된 힙 파일 : 나이 기준으로 정렬되어 있다면, 10000개의 페이지를 이분탐색으로 찾아야 하므로 log₂ 10000 만큼의 페이지를 불러와서 확인해보며 이 페이지에 찾고자 하는 범위의 나이대 사람이 존재하는지 확인한다.

이렇게 해서 하나의 페이지를 결정했다면 그 페이지에서 발견한 그 data row 부터 100개의 연속한 row를 가져오면 된다.

정렬이 되어있기 때문이다! 따라서 최종적으로 조회해야 하는 페이지의 수는 log₂ 10000 + 4~5 이다.

(log₂ 10000 페이지를 찾으면서 최종 찾은 페이지 1개에 최대 20개 row, 나머지 80개 row를 찾기 위해 추가적으로 4개 page 를 가져와야 하며, 만약 row 가 중간에 걸쳐있다면 1개의 페이지를 추가로 더 봐야할 수도 있다.)

 

군집 인덱스 : 나이를 search key 로 하여 인덱스가 존재한다면 찾고자 하는 범위의 시작점 인덱스를 집어 해당 위치의 데이터가 가리키는 페이지를 불러온다. 그리고 그 페이지부터 연속된 추가적으로 4~5개의 페이지를 가져오면 되므로 최종적으로 5~6개의 페이지를 불러온다.

 

예를 들어 10 ~ 34살 사이의 사람 데이터를 가져온다면, 10살 데이터가 존재하는 페이지를 불러온 뒤, 그 10살 데이터가 존재하는 row로부터 연속된 100개의 row를 조회하면 된다. (군집 인덱스는 데이터도 인덱스와 동일하게 정렬이 되어있으므로)

 

비군집 인덱스 : 비군집 인덱스의 경우, 인덱스는 정렬되어있더라도 실제 데이터는 정렬되어 있지 않을 수 있다.

최악의 경우, 각 인덱스가 가리키는 100개의 데이터가 모두 서로 다른 페이지에 존재할 수도 있다.

따라서 비군집 인덱스의 경우 5 ~ 100개의 페이지를 불러와야 한다.

 

---

 

이번에는 같은 상황에서 '인덱스 정보' 를 얻기 위해 몇 개의 페이지를 불러와야 하는지 생각해보자.

이때 하나의 페이지에는 200개의 인덱스 엔트리가 저장될 수 있다고 해보자. (인덱스의 크기는 포인터일 뿐이므로 작기 때문)

 

힙 파일 & 정렬된 힙 파일 : 0개

 

이 두 방식은 인덱스를 사용하지 않으므로, 인덱스 엔트리를 불러올 일이 없다.

 

군집 인덱스 : 1개

 

비군집 인덱스 : 1개 ~ 2개

 

군집 인덱스는 인덱스가 가리키는 데이터 하나만 가져오면 그로부터 연속된 100개의 데이터를 가져와서 파악할 수 있으므로 1개의 페이지를 로딩해서 하나의 인덱스 정보만 알아오면 된다.

 

비군집 인덱스는 최악의 경우 100개의 인덱스가 가리키는 데이터를 가져와야 하므로 1~2개의 페이지를 가져와서 연속된 100개의 인덱스 정보를 가져와야 한다. (인덱스는 모여있으나, 인덱스가 가리키는 데이터는 흩어져있으므로, 100개의 인덱스가 모두 필요한 것이다.)