[데이터베이스] 18. 힙 파일, 정렬된 파일, 군집/비군집 인덱스

DBMS에서 디스크로부터 읽어온 데이터를 저장하는 방식은 다양하다.

이번 글에서는 다양한 저장 방식의 종류와 특징에 대해 정리한다.

 

힙 파일

DBMS에서 데이터를 저장하는 제일 간단한 파일 구조이다. (자료구조 힙과는 관련이 없다.)

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

 

힙 파일에는 이런 페이지가 여러개 모여 저장된다.

그리고 각 페이지를 저장할 때는 그냥 들어온 순서에 맞춰 차곡차곡 저장하므로,

특정 기준에 의해 정렬되어있다거나 하지는 않는다.

 

이제 이렇게 데이터를 저장한 상태에서 DBMS의 기능인 데이터 조회, 수정, 삭제 연산을 생각해보자.

 

만약 힙 파일로 DBMS에 데이터를 저장해둔 상태에서 특정 레코드를 조회, 수정하는 경우,

그 레코드가 위치한 페이지를 찾기 위해서 힙 파일에 저장된 모든 페이지를 다 읽어봐야한다.

 

만약 힙 파일로 저장해둔 상태에서 레코드를 추가하는 경우, 그냥 맨 뒤에 추가하면 되므로 데이터 추가는 빠르게 일어난다.

 

데이터를 삭제하는 경우에는 삭제할 데이터를 찾기 위해 모든 페이지를 읽어봐야 하는 것은 물론, 데이터를 삭제한 이후에 그 자리는 구멍처럼 뚫려있으므로, 뒤의 데이터를 앞으로 한 칸씩 옮기는 작업을 해야한다.

이런 비용을 줄이기 위해 fill factor 라고 해서, 중간에 비어있는 저장 공간을 둘 수도 있다.

 

이처럼 힙파일은 데이터를 저장하는 것은 빠르지만 조회, 수정, 삭제 시 많은 비용이 발생해서 좋지 않다.

 

 

정렬된 힙 파일

기존의 힙 파일은 데이터를 저장하기만 하고 조회, 수정, 삭제가 잘 일어나지 않는 경우에는 유용하다.

정렬된 힙 파일은 저장하는 페이지들을 일정 기준에 맞춰 정렬된 상태를 유지한 채로 저장한다.

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

 

이렇게 저장하면 특정 데이터를 조회할 때 이분 탐색을 통해 훨씬 빠르게 탐색할 수 있다.

 

데이터를 추가할 때는 데이터를 추가할 페이지를 이분탐색을 통해 찾는다.

그리고 페이지에 적절한 위치에 레코드를 추가한 뒤, 나머지 레코드를 뒤로 밀어낸다.

이 뒤로 밀어내는 과정 때문에 정렬된 힙 파일은 삽입할 때 시간이 오래 걸린다.

그래서 fill factor 를 사용하여 미리 조금 비워두자는 아이디어도 있고,

chain page 아이디어를 사용하여 신규 레코드가 삽입될 때 그 자리가 부족하다면 새로운 페이지를 만들어 저장하고 그 페이지를 기존에 저장하려던 페이지와 연결하는 방법을 쓰기도 한다.

이 경우에는 데이터를 탐색하는데 시간이 오래 걸리게 된다.

 

최종적으로 데이터를 저장할 때는 '페이지 단위'로 데이터가 저장된다.

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

 

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

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

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

 

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

 

 

인덱스

기존의 힙 파일과 정렬된 힙 파일에는 '인덱스' 개념이 존재하지 않았다.

인덱스는 튜플을 찾기 위한 탐색 기준 어트리뷰트인 search key를 가지며, 이 탐색키는 꼭 하나의 튜플을 유일하게 식별할 필요는 없다.

 

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

데이터를 저장할 때 인덱스와 인덱스가 가리키는 실제 데이터를 하나의 파일에 통합해서 저장할 수도 있고, 분리해서 저장할 수도 있다.

통합된 경우를 integrated 라고 부르고, 분리된 경우 분리된 데이터 테이블을 세컨더리라고 부른다.

 

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

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

 

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

 

군집 인덱스

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

인덱스의 정렬 상태와 실제 데이터의 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개의 인덱스 정보를 가져와야 한다.