Data Storage Structures, indexing 요약

이 포스팅은 Database System Concepts(Abraham) 책을 참조하여 작성하였습니다.

Data Storage Structures

• 파일을 논리적으로 다스크 블록들에 매핑되는 레코드들의 시퀀스롤 구성할 수 있습니다.
  데이터베이스를 파일로 매핑하기 위한 방식중 하나는, 여러 파일을 사용하고, 어떠한 주어지 파일에 하나의 고정된 길이의 레코드로 저장을 합니다.
  다른 방법은 레코드를 위한 다양한 길이를 수용합니다. slotted-page 방식은 디스크 블록에서 가변 길이의 레코드를 다루기 위해 주로 사용되는 방식입니다.
• 데이터가 디스키와 메모리 사이에서 하나의 블록 단위로 전송되기 때문에, 파일 레코드에서 단일 블록에 관련된 레코드들로 저장을하는 것이 효과적입니다.
  만약 하나의 블록 접근을 가지고 여러 레코드에 접근할 수 있으면 디스크 엑세스를 많이 줄일 수 있습니다.
  디스크 접근은 일반적으로 디비 시스템의 병목을 만들기 때문에, 블록에 레코드를 잘 할당하는 것은 성능에 많은 영향을 줍니다.
• data dictionary (system catalog)는 메타데이터의 트랙을 유지합니다. (데이터들에 관련된 정보)
• 디스크 접근의 수를 줄이는 방법은 가능한 많은 블록들을 메모리에 유지하는 것입니다.
  모든 블록을 메모리에 유지할 수 없기 때문에, 블록 저장을 위한 메모리 공관 할당을 잘 관리해야 합니다.
  buffer 는 디스크 불록의 복사본을 저장하는 메모리의 파트입니다.
  버퍼 공간의 할당을 관리하는 subsystem 을 buffer manager 라고 합니다.
• Column 기반 저장 시스템은 데이터 warehousing application 에서 좋은 퍼포먼스를 보입니다.

Indexing

• 대부분의 쿼리들은 파일의 레코드에서 작은 부분만 참조합니다.
  이러한 레코드들을 찾는 오버헤드를 줄이기 위해서 디비를 저장하는 파일의 indices 생성합니다.
• 두가지 종류의 indice 를 사용할 수 있습니다. - dense/sparse indices
  Dense indices 는 모든 search-key value 에 대한 엔트리들을 포함합니다.
  Sparse indices 는 일부의 search-key value 에 대한 엔트리들을 포함합니다.
• 서치 키의 정렬 순서가 릴레이션의 정렬 순서와 일치하면, 그 서치 키의 index 를 clustering index 라고 합니다.
  그렇지 않은 indices 를 nonclustering 이나 나 secondary indices 라고 합니다.
  Secondary indices 는 clustering index의 검색 키가 아닌 검색 키를 사용하는 쿼리의 성능을 향상시킵니다. 그러나 디비의 수정이 있을 때 오버헤드가 발생합니다.
• index-sequential file 은 디비 시스템에서 사용되는 가장 오래된 index 스키마 중 하나입니다.
  검색 키 순서로 레코드를 빠르게 검색 할 수 있도록 레코드가 순차적으로 저장되고 비 순차 레코드가 함께 연결됩니다.
  빠른 랜덤 액세스를 허용하기 위해 인덱스 구조를 사용합니다.
• index-sequential file 의 주 단점은 파일이 커짐에 따라 성능이 저하된다는 것 입니다.
  이를 극복하기 위해 B+ tree index 를 사용합니다.
• B+tree index 는 밸런스 트리의 형태를 취합니다. 이는 루트까지의 모든 경로가 동일한 길이릐 트리입니다.
  B+tree 는 릴레이션에서 레코드의 수 N 을 밑으로 하는 로그 스케일에 비례합니다. - 각 nonleaf 노드는 N 개의 포인터를 저장합니다.
  N 의 값은 주로 50에서 100정도 됩니다.
  B+tree 는 balance 이진 트리 구조보다 더 짧습니다. - record 를 위치시키기 위한 디스크 접근이 더 적다.
• B+ 트리 조회는 간단하고 효율적입니다. 그러나 삽입과 삭제는 다소 복잡하지만 여전히 효율적입니다. B- 트리에서 조회, 삽입 및 삭제에 필요한 연산의 수는 각 비 리프 노드가 N 개의 포인터를 저장하는 관계에있는 레코드 수의 밑수 N에 대한 로그에 비례합니다.
• B+ 트리를 사용하여 레코드를 포함하는 파일을 색인화하고 레코드를 파일로 구성 할 수 있습니다.
• B- 트리 인덱스는 B+ 트리 인덱스와 유사합니다. B- 트리의 주요 이점은 B- 트리가 검색 키 값의 중복 저장을 제거한다는 것입니다. 주요 단점은 전체적인 복잡성과 주어진 노드 크기에 대한 팬 아웃 감소입니다. 시스템 설계자는 거의 보편적으로 실제로 B- 트리 인덱스보다 B- 트리 인덱스를 선호합니다.
• 해싱은 메인메모리 뿐아니라 disk 기반 시스템에서 인덱스들을 생성하기 위해 사용되는 테크닉 입니다.
• B+와 같은 Ordered indices 들은 단일 속성들을 포함하는 동일 한 조건을 기반으로 selection 에 대해 사용될 수 있습니다.
• selection 조건에서 포함되는 여러 attribute 들이 있을 때, 여러 인덱스에서 검색된 레코드 식별자를 교차 할 수 있습니다.
• 기본 B- 트리 구조는 초당 매우 많은 수의 임의 쓰기 / 삽입을 지원해야하는 애플리케이션에 적합하지 않습니다. 로그 구조 병합 트리 및 버퍼 트리를 포함하여 쓰기 / 삽입 비율이 높은 워크로드를 처리하기 위해 여러 가지 대체 인덱스 구조가 제안되었습니다.
• 비트 맵 인덱스는 고유 한 값이 거의없는 속성을 인덱싱하기위한 평균 압축 표현을 제공합니다. 교차 작업은 비트 맵에서 매우 빠르므로 여러 속성에 대한 쿼리를 지원하는 데 이상적입니다.
• R- 트리는 B- 트리의 다차원 확장; R- 트리 및 R *-트리와 같은 변형으로 공간 데이터베이스에서 인기가 있음이 입증되었습니다. 쿼드 트리와 같이 정기적으로 공간을 분할하는 인덱스 구조는 공간 조인 쿼리를 처리하는 데 도움이됩니다.
• 공간 인덱스 및 간격 B- 트리 특수 인덱스의 사용을 포함하여 시간 데이터를 인덱싱하기위한 많은 기술이 있습니다.