파일 구성과 인덱싱

개요

---

필자는 데이터베이스에 대해 자세하게 배우기 전까지는 우리가 넣은 데이터들이 들어가는 공간에 대해 생각한 적이 없었다.

어딘가로 들어가는 건 알겠는데 그 어딘가에 대한 개념이 상당히 모호하고, 마치 블러처리된 느낌이었다.

하지만 데이터베이스를 사용하고 이를 통해 개발을 한다면 정확히 알아야할 필요가 있다.

그렇다면 저장장치와 데이터베이스가 관련이 있는건 알겠는데, 정확히 어떤 이유 때문에 저장장치에 대해 알아야할까?

데이터베이스에서는 데이터를 저장할 때 다양한 저장장치를 사용할 수 있다.

대표적으로는 하드디스크(HDD), 솔리드 스테이트 디스크(SSD), 메모리(RAM)과 같은 것들이 있다.

데이터베이스 관리자는 이러한 저장장치들의 특성을 이해하고, 이를 데이터베이스 설계와 운영에 활용함으로써 데이터베이스의 성능을 최적화하고, 안정성을 유지할 수 있다.

예를 들면, HDD는 SSD에 읽고 쓰는 속도는 느리지만 가격이 싸서 같은 비용으로 SSD보다 더 많은 용량을 구성할 수 있다.

만약에 해당 데이터베이스가 속도보다는 용량이 중요하다면 SSD보다는 HDD로 저장장치를 구성하는 것이 좋다.

저장장치에는 완벽한 상위호환이라는 개념이 존재하지 않기 때문에 상황에 맞게 적절한 저장장치를 골라서 사용해야하며, 적절한 저장장치를 고르기 위해서는 어떤 것들이 있는지, 그 특징은 무엇인지 알아야 한다.

 

 

외부 저장장치상의 데이터

---

DBMS는 방대한 양의 데이터를 저장하며 데이터는 프로그램이 실행되는 동안에는 지속이 되어야한다.

따라서 데이터는 디스크나 테이프와 같은 외부 저장장치에 저장이 되다가, 데이터 처리가 필요해지면 주 기억장치로 불러온다.

디스크에서 읽고 쓰는 정보의 단위를 페이지라고 하며, 페이지의 크기는 대체로 4KB나 8KB다.

페이지 입출력 비용이 데이터베이스 연산들의 비용의 대부분을 차지하기 때문에 데이터베이스 시스템들은 이 비용을 최소화하도록 최적화한다.

디스크에 물리적으로 저장되는 방법가 주 기억장치가 이용되는 방법에 대해서 알기 위해서는 아래의 핵심 포인트는 굉장히 중요하다.

 

핵심 포인트

핵심 포인트 3가지를 알고 들어가자.

 

1. 디스크 (Disks)

디스크는 가장 중요한 외부 저장장치로, 고정된 비용으로 임의 페이지를 검색할 수 있다.

임의 페이지를 검색할 수 있다는 것은 Random Access라는 특성으로, 디스크에서 데이터를 읽을 때는 데이터가 저장된 위치와 상관없이 동일한 시간이 소요된다는 것이다.

하지만 여기에는 아래의 단점들이 존재한다.

1. 디스크는 회전하는 원판 위에 자기 헤드가 움직여 데이터를 읽고 쓰기 때문에, 읽기/쓰기 시간이 상대적으로 느리다.따라서 데이터를 순차적으로 읽는 것 보다 자원이 많이 들 때가 있다.
2. 특히, 랜덤 액세스(Random Access)에서는 헤드의 이동 시간이 추가로 소요되기 때문에 읽기 속도가 더욱 느려진다.
3. 디스크에서 랜덤 액세스를 많이 하게 되면, 디스크의 성능이 급격히 저하될 수 있다.대용량 데이터에서 랜덤 엑세스를 하기 위해서는 더 많은 헤드의 움직임을 필요로 하기에, 랜덤 액세스 요청이 많아지면 부하가 걸리게 되어 성능 저하가 급격하게 일어날 수 있다.
4. 디스크는 일반적으로 대용량 데이터를 저장할 때 사용된다.

 

2. 테이프 (Tapes)

연속적으로만 페이지를 읽을 수 있다.

이 말은 9번째에 있는 데이터를 읽기 위해서는 0번부터 순차적으로 하나씩 읽어야한다는 것이다.▼

테이프는 순차적으로 모든 데이터를 읽어야한다.

 

 

“너무 비효율적인거 같은데 사용하는데가 있나요?”

 

 

테이프는 디스크보다 저렴하며, 데이터를 수시로 읽고 쓰는 용도로 사용하지 않고 단순 아카이빙(보관용)용도로 사용된다.

 

3. 레코드 id(rid)

파일에서 각 레코드는 rid라고 불리는 유일 식별자를 가지고 있다.

rid는 그 레코드를 포함하고 있는 페이지의 디스크 주소를 식별할 수 있는 성질을 갖는다.

전체적으로 이런 계층구조를 보인다.▼

Storage > Page > Record.

 

 

Storage Manager

데이터는 처리를 위해 메모리로 읽히거나, 디스크에 기록이 된다.

이 과정은 버퍼 관리기라고 불리는 소프트웨어에 의해 수행이 된다.

그리고 디스크에 기록을 하는 것은 디스크 공간 관리기에 의해서 관리가 된다.

저장공간 관리는 버퍼 관리기와 공간 관리기에 의해 이루어진다고 말할 수 있다.

 

 

파일 구성과 인덱싱

---

레코드 파일

레코드 파일(file of records)은 DBMS에서 중요한 추상화이다.

파일은 생성되고 소멸되며, 레코드를 삽입하고 삭제할 수 있다.

또한 스캔(Scan)을 지원하여 한번에 하나씩 파일의 모든 레코드들을 살펴볼 수 있다.

 

파일 구조

파일 구조의 대표적인 것들로는 Heap file, Sorted file, Index가 있다.

 

Heap File

Heap file은 레코드를 추가할 때 디스크의 빈 공간에 차례대로 추가하는 방식이다.

레코드의 순서와 저장 위치는 무작위(random)하게 결정된다.

검색 시 모든 레코드를 순차적으로 읽어야 하므로 검색 속도가 느리다.

추가, 삭제, 수정 작업은 빠르지만, 검색 작업은 느리다.

특히, 대용량 데이터 처리 시 메모리 부족 문제가 발생할 수 있다.

 

Sorted File

Sorted file은 레코드를 정렬된 상태로 저장하는 방식이다.

검색 시 이진 검색(binary search)을 사용하므로 검색 속도가 빠르다.

추가, 삭제, 수정 작업은 레코드의 순서를 유지하기 위해 추가 작업이 필요하므로 느리다.

정렬된 상태를 유지하므로 레코드를 찾는 검색 작업은 빠르다.

 

Index

Index는 레코드 검색을 빠르게 하기 위해 사용되는 자료구조다.

인덱스는 검색에 사용되는 컬럼(column)의 값을 기준으로 생성된다.

검색 시 인덱스를 사용하여 레코드를 빠르게 찾을 수 있다.

인덱스를 유지하기 위해 추가, 삭제, 수정 작업 시 추가적인 작업이 필요하므로, 이러한 작업은 비교적 느리다.

대용량 데이터 처리 시 메모리 부족 문제가 발생할 수 있다.

이 중에서 인덱스에 대해 조금 더 자세하게 알아보자.

 

인덱싱

인덱스의 데이터 엔트리

우리는 입력하고자 하는 데이터를 다음과 같은 형태들로 저장할 수 있다.

 

1. 첫번째 방식 - key value와 data record로 구성하는 방식
2. 두번째 방식 - key value와 data record id (rid)로 구성하는 방식
3. 세번째 방식 - key value와 data record id (rid)의 list로 구성하는 방식

 

데이터 항목 대안 선택은 주어진 키 값을 가진 데이터 항목을 찾는 데 사용되는 인덱싱 기술과 연관되어있다.
(B+ tree, Hash)

일반적으로 인덱스에는 검색을 원하는 데이터 항목으로 이동하는 보조 정보가 포함된다.

이런 인덱스는 특별한 파일 구성으로도 볼 수 있기에, 이런 인덱스 파일 구성(index file oraganization)은 정렬 파일이나 비순서 레코드 파일을 대신해서 사용될 수 있다.

 

첫번째 방식

이 방식을 사용하면 인덱스 구조는 Heap file 또는 Sorted file이 된다.

특정 데이터 레코드 집합에 대해 한 인덱스는 하나의 레코드만을 가질 수 있다.

만약 한 인덱스가 여러 개의 레코드를 가지게 되면 데이터 레코드가 중복 저장되어 저장 공간이 낭비되고 일관성 문제가 발생할 수 있기 때문이다.

또한 데이터 엔트리를 데이터 레코드 자체로 저장하는 탓에, 데이터 레코드가 매우 큰 경우에는 데이터 엔트리가 포함된 페이지 수가 많아지므로 인덱스의 보조 정보의 크기도 커지게 된다.

 

두번째, 세번째 방식

두번째, 세번째 방식의 데이터 엔트리는 일반적으로 데이터 레코드보다 훨씬 작다.

2번과 3번 방식에서는 data entry가 데이터 레코드의 포인터를 가지고 있기 때문에, 데이터 레코드의 실제 위치를 가리키는 포인터만 저장하면 된다는 장점이 있다.

이로 인해 파일 구성과는 독립적으로 index를 구성할 수 있으며, 이전 방식인 1번보다 데이터 entry의 사이즈가 작아진다.

3번 방식은 2번 방식보다 더 작은 사이즈로 구성될 수 있지만, 데이터 entry들의 길이가 가변적이기 때문에 이러한 장점에도 불구하고 몇몇 단점이 존재한다.

 

군집 인덱스(Clustered Index)

군집 인덱스는 인덱스를 만들 때 데이터 레코드의 물리적인 순서와 인덱스의 순서를 일치시키는 것이다.

즉, 특정 컬럼에 대해 클러스터링 인덱스를 생성하면 해당 컬럼 값을 가지고 있는 데이터 레코드가 물리적인 순서대로 정렬된다.

 

특징

• 클러스터링 인덱스는 범위 검색에 유용하다.
• 범위 검색이란, 특정 범위의 값을 검색하는 것을 말하는데, 클러스터링 인덱스를 사용하면 검색 범위에 해당하는 인덱스 블록만 읽으면 되므로 처리 속도가 빨라진다.
• 클러스터링 인덱스는 한 테이블당 하나만 생성할 수 있으며, 생성된 컬럼 값에 따라서 레코드의 물리적인 순서가 달라진다.
• 따라서, 테이블에서 자주 사용되는 컬럼에 대해 클러스터링 인덱스를 생성하는 것이 좋다.

 

비군집 인덱스(Unclustered Index)

비군집 인덱스는 인덱스를 만들 때 데이터 레코드의 물리적인 순서와 인덱스의 순서를 일치시키지 않는 것이다.

즉, 특정 컬럼에 대해 언클러스터드 인덱스를 생성하면 해당 컬럼 값을 가지고 있는 데이터 레코드가 물리적인 순서대로 정렬되지 않는다.

 

특징

• 언클러스터링 인덱스는 데이터를 검색할 때 인덱스 블록을 읽은 후 데이터 레코드를 찾아야 하므로 처리 속도가 느리지만, 인덱스의 크기가 작고 여러 개 생성할 수 있기 때문에 데이터 수정 작업에 대한 부담이 적다.
• 언클러스터링 인덱스는 일반적으로 테이블에서 자주 검색되는 컬럼에 대해 생성된다.
• 인덱스를 생성할 때 해당 컬럼의 값을 기준으로 인덱스를 정렬한다.

 

clustered는 data entry와 data file이 정렬되어있는 반면, unclustered는 정렬되어있지 않다.

 

둘의 결정적인 차이점

테이블의 주요 키(primary key)를 기반으로 데이터를 물리적으로 정렬하느냐 안하느냐의 차이점이 있다.

Clustered index는 물리적으로 정렬을 하는 반면, unclustered index는 물리적으로 정렬하지 않는다.

 

기본 인덱스(Primary Index)

Primary Index는 데이터베이스 테이블에서 기본키(primary key)를 기반으로 생성되는 인덱스이다.

기본키는 테이블에서 각 레코드를 유일하게 식별할 수 있는 Column 또는 Column의 조합이다.

 

보조 인덱스(Secondary index)

Secondary Index는 Primary Index가 아닌 다른 열을 기반으로 생성되는 인덱스이다.

하나의 테이블에 여러 개의 Secondary Index를 생성할 수 있으며, 각각의 Secondary Index는 다른 컬럼을 기반으로 생성될 수 있다.

 

+) Unique(고유 인덱스)

검색 키에 후보 키가 포함된다.

 

 

인덱스 자료 구조

---

인덱스는 위에도 나와있듯이 레코드 검색을 빠르게 하기 위해 사용되는 자료구조다.

자주 조회되는 Column 에 대한 Index Table을 따로 만들어 SELECT 문이 들어왔을 때 Index 테이블에 있는 값들로 결과 값을 조회한다.

인덱스의 특징은 다음과 같다.

1. 파일에 대한 인덱스는 해당 파일에 있는 레코드의 검색 키를 빠르게 처리하기 위한 자료구조로, 검색 키를 참조하면 해당 레코드를 찾을 수 있는 포인터를 제공한다.
   이를 통해 검색 속도를 빠르게 할 수 있다.
   
   • 관계(relation)의 모든 필드의 하위 집합은 관계에 대한 인덱스의 검색 키가 될 수 있다.
     즉, 특정 필드가 아니더라도 필드의 조합으로도 검색 키를 만들 수 있다.
   • 검색 키는 관계 내에서 레코드를 고유하게 식별하는 데 사용되는 키(key)와 동일하지 않다.키는 해당 레코드를 찾기 위한 유일한 식별자로 사용되는 반면, 검색 키는 특정 레코드를 찾기 위해 사용되는 필드나 필드의 조합이다.
   • 검색 키는 레코드를 고유하게 식별하지만, 이는 키(key)와 동일하지 않다.
2. 인덱스는 데이터 엔트리(data entries) 컬렉션을 포함하며, 검색 키를 이용하여 데이터 엔트리를 찾을 수 있다.
   이를 통해 검색 속도를 높일 수 있다. 
   • 데이터 엔트리 k*가 주어지면, 하나의 디스크 I/O에서 최대 하나의 키 k와 관련된 레코드를 찾을 수 있다.
     인덱스를 이용하여 검색할 때, 디스크 I/O를 최소화하면서 원하는 레코드를 빠르게 찾을 수 있다.

 

대표적은 인덱싱 방법으로는 B+ Tree와 Hash가 있다.

 

B+ Tree Indexing

B+ 트리는 대량의 데이터를 저장하고 빠르게 검색할 수 있는 자료구조로, 데이터베이스에서 인덱스를 구현하는 데 매우 효율적이다.

B+ 트리는 이진 검색 트리와 유사하지만, 각 노드에는 여러 개의 키와 해당 키에 대한 포인터가 있다.

이러한 포인터는 주로 다른 노드를 가리키는데 사용된다.

B+ 트리는 리프 노드만이 실제 데이터를 포함하며, 리프 노드는 키 값에 따라 오름차순으로 정렬된다.

또한 모든 리프 노드는 동일한 레벨에 존재한다.

따라서 B+ 트리에서는 특정 범위 내의 모든 데이터를 순차적으로 검색하는 것이 매우 빠르다.▼

B+ 트리 예시

 

 

B+ 트리는 검색, 삽입, 삭제 작업을 수행하는 데 O(log n)의 시간 복잡도를 갖는다.

또한 키 범위 검색과 정렬된 결과 검색에 효율적이다.

하지만 B+ 트리는 메모리 내부 구조를 유지하는 것이 중요하기 때문에, 자주 사용되는 데이터는 메모리 내부에 캐시되는 것이 성능에 큰 영향을 미친다.

 

Hash Indexing

해시 인덱싱은 해시 함수를 사용하여 인덱스를 생성하는 인덱싱 방법 중 하나다.

해시 함수는 입력 값으로부터 고정 크기의 해시 코드를 생성하는 함수다.

해시 인덱싱에서는 각 레코드의 해시 코드를 인덱스 값으로 사용한다.▼

해시 인덱싱

 

 

해시 인덱싱은 매우 빠른 검색 속도를 제공하지만, 몇 가지 제한 사항이 있다.

1. 해시 함수가 충돌이 발생할 가능성이 있다.이 경우, 이러한 레코드를 구별하기 위해 충돌을 해결하기 위한 추가적인 작업이 필요하다.
2. 즉, 두 개 이상의 레코드가 동일한 해시 코드를 가지는 경우가 발생할 수 있다.
3. 해시 인덱스는 범위 검색에는 적합하지 않다.
4. 인덱스에서 키 값의 범위를 지정하여 검색하는 것은 불가능하며, 키 값의 정확한 일치 검색만 가능하다.

따라서 해시 인덱싱은 키 값이 일치하는 검색이 자주 발생하고 범위 검색이 필요하지 않은 경우에 적합하다.

이 둘은 아래의 링크에서 더 자세히 볼 수 있다. ▼

B+ Tree

 

 

파일구성의 비교

---

데이터베이스에서 연산의 비용은 굉장히 중요하다.

그렇기에 어떤 상황에서 어떤 파일 구성의 비용이 적게 나오는 지를 알고 있어야한다.

지금부터는 여러 가지 기본적인 파일 구성을 놓고 직원 레코드들에 대한 몇가지 연산의 비용을 비교할 것이다.

 

파일 구조

• 랜덤 순서로 되어 있는 직원 레코드 파일, 즉 힙 파일
• <age, sal>에 의해 정렬되어 있는 직원 레코드 파일
• 검색 키로 <age, sal>을 가지는 군집 B+ 트리 파일
• <age, sal>에 대한 비군집 B+ 트리 인덱스를 가지는 힙 파일
• <age, sal>에 대한 비군집 해시 인덱스를 가지는 힙 파일

 

수행할 비교 연산

• 스캔
• 등호 셀렉션 탐색
• 범위 셀렉션 탐색
• 레코드 삽입
• 레코드 삽입

 

	Scan	Equality	Range	Insert	Delete
Heap	BD	0.5 BD	BD	2D	Serach + D
Sorted	BD	Dlog_2(B)	D (log_2 (B) + #pgs with match recs)	Search + BD	Search + BD
Clustered	1.5BD	Dlog_F(1.5B)	D (log_F (1.5B) + #pgs with match recs)	Search + D	Search + D
Unclustered Tree index	BD(R + 0.15)	D(1 + log_F(0.15B))	D (log_F (1.5B) + #pgs with match recs)	Search + 2D	Search + 2D
Unclustered Hash index	BD(R + 0.125)	2D	BD	Search + 2D	Search + 2D