[데이터베이스] 버퍼와 인덱싱 개념과 종류 (Buffer and index in DBMS)

데이터베이스 버퍼와 인덱싱

데이터베이스 시스템에서 버퍼 관리와 인덱싱은 성능 최적화에 있어 매우 중요한 요소입니다. 이 글에서는 버퍼 매니저의 역할과 인덱싱의 기본 개념에 대해 설명하겠습니다.

버퍼와 버퍼 매니저

버퍼의 개념

데이터베이스에서 블록(Block)은 저장소 할당과 데이터 전송의 기본 단위입니다.

디스크와 메모리 사이의 블록 전송 횟수를 최소화하는 것이 데이터베이스 시스템의 목표이며, 이를 위해 가능한 많은 블록을 메인 메모리에 유지해야 합니다.

버퍼(Buffer)는 디스크 블록의 복사본을 저장하기 위해 사용 가능한 메인 메모리의 일부분입니다.

즉, 버퍼는 메모리 공간을 의미합니다.

버퍼 매니저(Buffer Manager)는 메인 메모리에서 버퍼 공간을 할당하는 역할을 담당하는 데이터베이스의 소프트웨어 모듈입니다.

버퍼 매니저의 역할

프로그램이 디스크의 블록을 필요로 할 때 버퍼 매니저를 호출합니다. 버퍼 매니저는 다음과 같이 동작합니다:

1. 요청된 블록이 이미 버퍼에 있다면, 버퍼 매니저는 메인 메모리에 있는 해당 블록의 주소를 반환합니다.
2. 요청된 블록이 버퍼에 없다면, 버퍼 매니저는 다음 작업을 수행합니다:
   • 버퍼에서 블록을 위한 공간을 할당합니다.
   • 필요한 경우 다른 블록을 대체(교체)하여 새 블록을 위한 공간을 확보합니다.
   • 교체된 블록은 수정되었을 경우에만 디스크에 다시 쓰여집니다.
   • 디스크에서 블록을 읽어 버퍼로 가져온 후, 요청자에게 메인 메모리에 있는 블록 주소를 반환합니다.

 

버퍼 매니저의 작동 방식

읽기(Read) 작업

1. 쿼리가 읽기 요청을 합니다.
2. 버퍼 매니저는 요청된 페이지를 버퍼 캐시에서 찾습니다.
3. 페이지가 버퍼에 없다면, 디스크에서 페이지를 가져오고 필요시 교체 정책에 따라 버퍼의 페이지를 교체합니다.
4. 교체될 페이지가 더티(Dirty) 상태라면 디스크에 기록합니다.
5. 버퍼 매니저는 페이지를 쿼리에 반환합니다.

 

쓰기(Write) 작업

1. 쿼리가 쓰기 요청을 합니다.
2. 버퍼 매니저는 요청된 페이지를 버퍼 캐시에서 찾습니다.
3. 페이지가 버퍼에 없다면, 디스크에서 페이지를 가져오고 필요시 교체 정책에 따라 버퍼의 페이지를 교체합니다.
4. 데이터를 버퍼에 있는 페이지에 씁니다.
5. 페이지는 더티(Dirty) 상태로 표시됩니다.

 

트랜잭션 커밋(Commit)

1. 쿼리가 커밋 요청을 합니다.
2. 버퍼 매니저는 더티 페이지들을 디스크에 플러시(flush)합니다.

 

버퍼 교체 정책

버퍼가 가득 찼을 때, 어떤 블록을 교체할지 결정하는 정책이 필요합니다:

핀된 블록(Pinned Block): 디스크에 쓰는 것이 허용되지 않은 블록입니다.

• 블록에서 데이터를 읽거나 쓰기 전에 핀을 설정합니다. 이는 "사용중이니까 버퍼에서 제거하지 마라"는 의미입니다. (cnt++)
• 읽기/쓰기가 완료되면 언핀(unpin)합니다. (cnt--)
• 여러 동시 핀/언핀 작업이 가능합니다.
• 핀 카운트를 유지하고, 핀 카운트가 0인 버퍼 블록만 제거할 수 있습니다.

버퍼에 대한 공유 및 독점 잠금(Shared and Exclusive Locks):

• 동시 작업 간의 충돌을 방지해야 합니다.
• 읽기 작업은 shared lock(read lock)을 얻습니다. 모든 read 스레드들이 사용 가능합니다.
• 쓰기 작업은 exclusive lock(write lock)이 필요합니다. writer를 추방하기 위해 존재합니다.
• 잠금 규칙:
  • 한 번에 하나의 프로세스(트랜잭션)만 exclusive lock을 얻을 수 있습니다.
  • shared lock은 exclusive lock과 동시에 존재할 수 없습니다.
  • 여러 프로세스가 동시에 shared lock을 얻을 수 있습니다.

 

버퍼 교체 정책의 종류

LRU(Least Recently Used)

대부분의 OS는 가장 오랫동안 사용되지 않은 블록을 교체합니다.

• LRU의 아이디어: 과거 블록 참조 패턴을 사용하여 미래 참조를 예측합니다.
• 그러나 LRU는 데이터베이스 쿼리에는 좋지 않을 수 있습니다.
• 예: join 계산 시 순차적으로 접근하는 패턴에서는 효율적이지 않습니다.

Toss-immediate 전략

블록 처리가 완료되자마자 해당 블록을 제거합니다.

MRU(Most Recently Used) 전략

블록이 처리된 후, 해당 블록이 교체 대상이 됩니다. 즉, 가장 최근에 사용된 블록을 교체합니다.

버퍼 매니저는 통계를 사용할 수도 있습니다. 예를 들어, 특정 테이블이 참조될 확률 같은 정보를 활용합니다. 데이터 사전은 자주 접근되므로, 이러한 블록을 버퍼에 유지하는 것이 좋은 전략입니다.

---

인덱싱(Indexing)

인덱싱의 개념

인덱싱은 데이터 접근 속도를 높이기 위해 사용됩니다. 인덱싱은 일종의 자료구조입니다. 도서관의 저자 카탈로그를 생각해보면 이해가 쉽습니다.

검색 키(Search Key)는 레코드를 찾는 데 사용되는 속성 집합입니다. 주로 Primary Key(PK)를 자주 사용합니다. 인덱스 파일은 다음 형태의 레코드(인덱스 항목이라 함)로 구성됩니다:

인덱스는 일반적으로 원본 테이블보다 훨씬 작습니다(검색 키와 포인터는 보통 8바이트 정도).

 

인덱스의 종류

두 가지 기본 유형의 인덱스가 있습니다:

1. 순서 인덱스(Ordered Indices): 키가 정렬된 순서로 저장됩니다. 이는 트리 구조를 갖습니다.
2. 해시 인덱스(Hash Indices): 검색 키가 "해시 함수(hash function)"를 사용하여 "버킷(buckets)"에 균등하게 분산됩니다. 여기서 버킷은 블록의 공간을 의미하고, 해시 함수는 버킷의 번호를 계산합니다.

 

인덱스 평가 지표

인덱스를 평가하는 데 사용되는 지표는 다음과 같습니다:

• 효율적으로 지원되는 Access types
  • 포인트 쿼리(key = value): 해시 인덱스가 유리합니다.
  • 범위 쿼리(low < key < high): 순서 인덱스가 유리합니다.
• Access time: 검색 키를 찾는 시간
• Insertion time
• Deletion time
• Space overhead: 메모리/저장소에서 인덱스가 차지하는 공간

 

순서 인덱스(Ordered Indices)

순서 인덱스에서는 인덱스 항목이 검색 키 값에 따라 정렬되어 저장됩니다.

클러스터드 인덱스(Clustered Index) 또는 Primary Index:

• 인덱스의 키 순서 = 파일의 순차적 순서

세컨더리 인덱스(Secondary Index) 또는 논클러스터드 인덱스(Nonclustered Index):

• 파일의 순차적 순서와 다른 순서를 지정하는 인덱스

인덱스-순차 파일(Indexed-Sequential File, ISAM):

• 파일의 레코드가 Search Key에 대해 정렬되어 있습니다.
• 검색 키에 따라 정렬된 순차 파일로, 검색 키에 대한 클러스터드 인덱스를 갖습니다.

 

밀집 인덱스(Dense Index)

밀집 인덱스는 파일의 모든 검색 키 값에 대해 인덱스 레코드가 존재합니다. 예를 들어, instructor 릴레이션의 ID 속성에 대한 인덱스가 있을 수 있습니다.

 

또한 dept_name을 기준으로 정렬된 instructor 파일에 대한 밀집 인덱스도 가능합니다.

 

희소 인덱스(Sparse Index)

희소 인덱스는 일부 검색 키 값에 대해서만 인덱스를 생성합니다. 이는 레코드가 검색 키에 따라 순차적으로 정렬되어 있을 때 적용 가능합니다.

검색 키 값 K를 가진 레코드를 찾으려면:

1. K보다 작은 가장 큰 검색 키 값을 가진 인덱스 레코드를 찾습니다.
2. 인덱스 레코드가 가리키는 레코드부터 순차적으로 파일을 검색합니다.

 

세컨더리 인덱스(Secondary Index)

instructor의 salary 필드에 대한 세컨더리 인덱스를 예로 들 수 있습니다. 인덱스 레코드는 특정 검색 키 값을 가진 모든 실제 레코드를 가리키는 포인터를 포함하는 버킷을 가리킵니다.

세컨더리 인덱스는 밀집(dense)해야 합니다.

이는 sparse 인덱스가 동일하지 않아도 적당한 시간에 찾을 수 있도록 사용되는 것인데, 세컨더리 인덱스는 인덱스 기준으로 정렬을 하지 않으므로 sparse 인덱스를 사용하면 인덱스의 의미가 없어지기 때문입니다.

 

다단계 인덱스(Multilevel Index)

인덱스가 메모리에 맞지 않으면 접근이 비싸집니다. 해결책은 디스크에 보관된 인덱스를 순차 파일로 취급하고 이에 대한 희소 인덱스를 구성하는 것입니다.

• 외부 인덱스(Outer Index): 기본 인덱스에 대한 희소 인덱스
• 내부 인덱스(Inner Index): 기본 인덱스 파일

외부 인덱스도 메인 메모리에 맞지 않으면 또 다른 수준의 인덱스를 만들 수 있으며, 이런 식으로 계속됩니다. 파일에 삽입이나 삭제가 있을 때는 모든 수준의 인덱스를 업데이트해야 합니다.