25 - 1/데이터베이스

08장 물리적 저장 구조와 인덱스

Raming 2025. 6. 6. 18:53

1. 데이터베이스의 물리적 저장구조

- 물리적 데이터베이스(physical database)

 

 

  • 테이블, 레코드들은 HDD에 저장
  • 운영체제가 관리하는 파일 시스템 이용
    1) 기본 저장 구조: 파일
    2) 입출력 단위: 블록(block)

 

 

 

 

- 테이블의 물리적 저장 구조

 

 

 

 

  • 블록
    1) 하나 이상의 레코드들 저장
    2) 각 블록, 하나의 테이블에 속함
  • 파일
    ➡️ 하나 이상의 테이블들이 저장

 

 

 

 

- 블록 내 레코드 저장 방식

(a) 전체 길이: 112bytes | (b) 전체 길이: 88bytes

create table course
(
      course_id      varchar2(4),
      title                varchar2(20),
      credit             int
)

 

- 클러스터링(clustering)

  • 자주 검색되는 필드 기준, 관련 레코드들을 같은 블록에 저장

 

2. 인덱스

- 인덱스(index)

  • 사용 이유
    1) 파일 내 레코드의 위치 빨리 찾기 위해
    2) 인덱스가 없으면 순차 검색해야 함
  • 예
    1) 도서관 책 정렬
    2) 사전 단어 정렬
    3) 전화번호부 이름 정렬
  • 빠른 검색을 위한 간단한 방법
    1) 검색 필드로 사전 정렬, 이진검색(binary search)
    2) 검색 필드의 종류가 많으면 별도의 검색 위한 자료구조 생성(인덱스) ➡️ 도서 뒷 부분의 (용어, 페이지) 구조

- 데이터베이스의 인덱스

 

 

 

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

 

 

 

- SQL과 인덱스

select      *
from        student
where      dept_id = '920' and address='서울'
  • student 테이블의 레코드 수: 10,000개
  • dept_id가 '920'인 레코드 수: 500개
  • 인덱스가 없을 경우
    1) 모든 레코드 순차 검색
    2) 10,000개 레코드 모두 검색
  • dept_id 필드에 인덱스 있을 경우
    1) dept_id가 '920'인 레코드만 검색
    2) 500개의 레코드만 검색
select      count(*)
from        student.s, department d
where      address='서울' and s.dept_id = d.dept_id
  • 처리 과정
    1) department 테이블을 순차적으로 검색하여 각 레코드의 dept_id 값에 대해 student 테이블의 dept_id에 대한 인덱스를 사용하여 student테이블의 레코드를 검색 (조인 연산)
    2) 검색된 레코드 중 address 필드 값이 '서울'인 레코드만 검색
    3) 3, 1, 2의 과정으로 검색된 레코드 수 모두 더함

- 기본키와 인덱스

  • 기본키
    1) 레코드 검색, 삽입, 삭제할 때 빈번하게 조회
    2) 기본키에 대해서 대부분의 DBMS가 자동으로 인덱스 생성
  • 장단점
    1) 장점: 검색 속도 ⬆️
    2) 단점
      1️⃣ 테이블에 레코드를 삽입하고 관련 정보를 인덱스에 갱신해야 함
      2️⃣ 인덱스가 많아지면 삽입, 삭제, 수정연산 속도 ⬇️
  • B+ 트리: RDBMS에서 인덱스로 자주 사용되는 자료구조

- 차수가 n인 B+ 트리 특징 (원리만 알고 O)

  • 차수: 한 노드(node)에서 하위 자식 노드(child node) 가리키는 주소의 개수
  • 차수가 n인 B+ 트리의 중간 노드 구조

 

     1) p1 ~ pn: 자식 노드 가리키는 포인터

     2) Key1 ~ Keyn-1: 검색키 (Key1 < key1 < ... < Keyn-1)

     3) Pi+1이 가리키는 모든 하위 노드들의 검색키, Keyi보다 크고 Keyi+1 보다 작음

  • 단말노드(leaf node)에 실제 레코드 주소 저장

- department 테이블의 B+ 트리 인덱스

 

- B+ 트리의 성능

  • department 테이블, 10,000개의 레코드 갖고, 이중에서 '컴퓨터공학과' 레코드 검색한다고 가정
  • 인덱스 없다면 최악의 경우 10,000개 검색
  • dept_name 필드에 차수가 10인 B+ 인덱스가 있다면 B+- 트리 높이는 최대 6 넘지 않음
    ➡️ 차수: 10 | 검색 키의 수: 10,000

 

- 복합 인덱스(composite index)

 

 

 

  • 두 개 이상의 필드에 대해 하나의 인덱스 생성
  • 엔트리들, 검색키 값의 순서대로 정렬 

 

 

 

- 엔트리 정렬 방법

  • 검색 키 값이 문자열인 경우 사전식 정렬 사용
  • 숫자인 경우 크기로 정렬
  • 문자열/숫자 아닌 경우 대소관계 정의 필요
  • 예제
    1) takes 테이블 스키마: (stu_id, class_id, grade)
    2) 복합 인덱스 검색 키: (stu_id, class_id)
    3) 검색 키, 문자열이므로 사전식 정렬 사용

- takes 테이블의 복합 인덱스 구성 예

 

- 인덱스의 종류 - 대응 밀집도

 

 

 

  • 희소 인덱스(sqarse index)
    ➡️ 테이블의 일부 레코드에 대해서만 인덱스 엔트리 생성
  • 밀집 인덱스(dense index)
    ➡️ 테이블의 모든 레코드에 대해 인덱스 엔트리 생성 

 

 

- 인덱스의 종류 - 클러스터링 유무 (중요)

 

  • 클러스터 인덱스(clustered index)
    1) 인덱스 엔트리 순서대로 레코드 저장
    2) 보통 기본키에 적용
    3) 하나의 테이블에 하나만 생성O
  • 비클러스터링 인덱스(non-clustered index)
    ➡️ 인덱스 엔트리 순서와 상관X 레코드 저장 

- 클러스터 인덱스

  • 범위 검색에 효과적
    select      name
    from        student
    where      stu_id between '1292001' and '1292303'
  • order by를 포함하는 질의에 효과적
    select      grade
    from        student
    where      stu_id between '1292001' and '1292303'

 

3. SQL을 이용한 인덱스의 설정

- 인덱스 생성 구문

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

  • dept_name의 값 중복되지 않을 경우
    1) create unique index dept_index on department(dept_name)
    2) 레코드 삽입 시 dept_name 값 중복되는지 자동 체크
  • 복합 인덱스 생성
    ➡️ create index student_index2 on student(name, address)

 

  • 인덱스 삭제 구문
    ➡️ drop index dept_index

 

- 언제, 어떤 필드에 인덱스를 만들어야 할까

  • 인덱스를 만들면 유리한 경우
    1) 테이블의 레코드 수 많을 때
    2) where절에 자주 사용되는 필드 ➡️ 검색 조건 or 조인 조건
    3) 조인 연산에 참여 or 널(null) 많은 필드
  • 인덱스를 만들면 불리한 경우
    1) 테이블 레코드 수 적을 때
    2) where 절에 거의 사용X 필드
    3) 삽입, 삭제, 수정이 자주 발생하는 테이블
    4) 서로 구별되는 유일 값 개수가 적은 필드(예: 성별)
      ➡️ Bitmap index