물리적 저장구조와 인덱스

<물리적 데이터 베이스(physical database)>
- 테이블과 레코드들은 HDD에 저장
- 운영체제가 관리하는 파일 시스템 이용
  - 기본 저장 구조는 파일
  - 입출력 단위는 블록(block) 

- 블록(block)
  - 하나 이상의 레코드들이 저장
  - 각 블록은 하나의 테이블에 속한다

- 파일
  - 하나 이상의 테이블들이 저장


<클러스터링(clustering)>
- 자주 검색되는 필드를 기준으로 관련 레코드들을 같은 블록에 저장


<인덱스(index)>
- 왜 사용할까?
  - 파일 내 레코드의 위치를 빨리 찾기 위해
  - 인덱스가 없으면 순차 검색해야 한다

- 인덱스의 예
  - 도서관의 책 정렬
  - 사전의 단어 정렬
  - 전화번호부의 이름 정렬



<데이터베이스의 인덱스>
- 레코드에 대한 물리적 저장위치를 별도로 기록
- 인덱스의 구조
  - 인덱스 엔트리 : (검색키, 주소)
  - 검색키 : 테이블에 속한 한 개 이상의 필드



<기본키와 인덱스>
- 기본키
  - 레코드의 검색, 삽입, 삭제할 때 빈번하게 조회된다
  - 기본키에 대해서는 DBMS가 자동으로 인덱스 생성

- 인덱스의 장단점
  - 장점
    - 검색 속도 향상

  - 단점
    - 테이블에 레코드를 사입하고 관련 정보를 인덱스에 갱신해야 한다
    - 인덱스가 많아지면 삽입, 삭제, 수정연산 속도 저하

- B+ 트리
  - RDBMS에서 인덱스로 자주 사용되는 자료구조



<차수가 n인 B+트리의 특징>
- 차수 
  - 한 노드(node)에 하위 자식 노드(child node)를 가리키는 주소의 개수
 
- 차수가 n인 B+트리의 중간 노드 구조
  P1 | Key1 | P2 | ... | P(n-1) | Key(n-1) | Pn
  - P1~Pn : 자식 노드를 가리키는 포인터
  - Key1~Key(n-1) : 검색키
  - P(i+1)이 가리키는 모든 하위 노드들의 검색키는 Key(i)보다 크고 Key(i+1)보다 작거나 같다



<복합 인덱스(composite index)>
- 두 개 이상의 필드에 대해 하나의 인덱스 생성
- 엔트리들은 검색키 값의 순서대로 정렬



<엔트리 정렬 방법>
- 검색 키 값이 문자열인 경우에는 사전식 정렬 사용
- 숫자인 경우에는 크기로 정렬
- 문자열/숫자가 아닌 경우에는 대소관계 정의 필요
- 예제 
  - takes 테이블 스키마 : (stu_id, class_id, grade)
  - 복합 인덱스의 검색 키 : (stu_id, class_id)
  - 검색 키가 문자열 이므로 사전식 정렬 사용
  (s1, c1) < (s2, c2)을 만족하려면, s1<s2 또는 (s1=s2)인 경우에는 c1<c2



<복합 인덱스 주의사항>
- 관련 필드의 순서에 따라 인덱스 효과가 달리짐
- (stu_id, class_id) 필드 순서에 효과적인 질의
- ex)
  select *
  from takes
  where stu_id = '1292001' and class_id>'C101-01'

- ex) (class_id, stu_id)필드 순서에 효과적인 질의
  select *
  from takes
  where stu_id > '1292001' and class_id='C101-01'



<해시 인덱스(hash index)>
- 해시 함수(hash function)를 기반으로 인덱스 엔트리를 구성하는 인덱스
- 버켓(bucket)
  - 인덱스 엔트리가 저장되는 공간
  - 버켓 번호 : 해시 함수 값



<해시 인덱스 구성 및 사용 방법>
- 인덱스 구성 방법
  - 인덱스 구성에 사용될 필드 결정
  - 필드 값에 해시 함수 적용하여 버켓 번호 생성
  - 인덱스 엔트리를 생성하여 해당 버켓에 저장

- 인덱스 사용 방법
  - 검색할 값을 해시 함수에 적용하여 버켓번호 생성
  - 해당 버켓안에 들어 있는 인덱스 엔트리 검색



<인덱스 생성 구문>
- 형식
  create index<인덱스이름> on <테이블이름>(<필드리스트>)

- department 테이블에서 dept_name에 인덱스 생성
  create index dept_index on department(dept_name)

- dept_name의 값이 중복되지 않을 경우
  create unique index dept_index on department(dept_name)
  - 레코드 삽입 시 dept_name값이 중복되는 지 자동으로 체크

- 복합 인덱스 생성
  create index student_index2 on student(name, address) //name은 1차 index, address는 2차 index



<인덱스 삭제 구문>
- 형식
  drop index<인덱스 이름>

- dept_index 삭제
  drop index dept_index



<언제, 어떤 필드에서 인덱스를 만들어야 할까?>
- 인덱스를 만들면 유리한 경우
  - 테이블의 레코드 수가 많을 때
  - where절에 자주 사용되는 필드
  - 조인 연산에 참여하는 필드

- 인덱스를 만들면 불리한 경우
  - 테이블의 레코드 수가 적을 때
  - where절에 거의 사용되지 않는 필드
  - 삽입, 삭제, 수정이 자주 발생하는 테이블
  - 서로 구별된느 유일 값의 개수가 적은 필드(예 : 성별)