2018/05/18 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 8강 데이터의 저장

2018/05/17 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 6강 정규형의 적용

2018/05/15 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 5강 정규화 기초

2018/03/21 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 4강 데이터베이스 언어

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 3강 관계형 모델

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 2강 데이터베이스 모델링

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 1강 데이터베이스의 이해

 

DBMS가 데이터를 가져오는 속도가 늦다면 쓰기 굉장히 싫어질꺼다... 비효율적

인덱스는 우리나라말로 찾아보기 라는 뜻이다.

인덱싱이 어떻게 내부적으로 구성되고 동작하여 DBMS가 데이터를 빠르게 찾아줄 수 있는지 알아보도록 하자.

1. 인덱싱

1) 데이터 검색 과정

  • 비효율적 과정
    디스크에 데이터 모음이 있다면~
    메모리에 블럭단위로 읽어와서 첫번째 레코드부터 검색 할 데이터가 있는지 검색하여 원하는 결과가 나올 때 까지 읽는다.

2) 인덱스의 개념

  • 데이터 검색에서 발생하는 비효율적인 문제를 해결을 목적으로 시작
    - 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 하는 데이터와 관련된 부가적인 구조
    - 인덱싱: 인덱스를 디자인하고 생성하는 작업
  • 인덱스와 검색키(특정컬럼값)를 통하여 레코드가 디스크 저장장치 또는 메모리의 어느 블럭에 저장되어 있는지 파악하고, 해당 블럭을 빠르게 적재한다.

검색키?
파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

  • 1번의 데이터 검색과정의 효율적인 과정
    메모리에 적재하기 전에 디스크에 인덱스를 생성 해 놓는다.
    예시)이름을 검색키로 놓고 각각에 해당하는 레코드가 어디있는지 포인터를 가지고 있다.
    메모리에 인덱스(검색키+포인터)를 적재(블럭단위 적재보다 더 많은 인덱스 데이터를 적재 가능)해서 검색한다.
  • 인덱스의 단점은 디스크에 추가적인 데이터(검색키 + 포인터)를 저장하기 때문에 용량을 조금 더 많이 먹는다가 단점이 될 수 있다.

3) 인덱싱의 개념

  • 인덱스의 종류
    - 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
    - 해시 인덱스: 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당되는지 결정
  • 인덱스의 평가기준
    - 접근 시간: 데이터를 찾는 데 걸리는 시간
    - 유지 비용: 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용
    - 공간 비용: 인덱스 구조에 의해 사용되는 부가적인 공간 비용

 

2. 순서 인덱스

1) 순서 인덱스의 특징

  • 검색키로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 순서 인덱스를 사용
    - 검색키를 정렬하여 해당 검색키와 관련된 레코드와의 연계를 통하여 인덱스 생성

2) 인덱스의 구성

  • 인덱스 엔트리의 구조


설명.
덱스 엔트리는 [검색키값] 과 [포인터]로 구성되어 있는데 [포인터]는 또 두 개의 항목,
[블럭ID] 와 [오프셋]으로 구성되어 있다.
예를 들어 검색키 값이 20140001이고 블럭ID가 b2 오프셋이 30이면
블럭ID가 b2 에서 30바이트만큼 떨어져 있는 곳에 20140001 이라는 검색키값을 가진
레코드가 있다 라는 뜻

  • 순서 인덱스의 분류
    - 밀집(dense) 인덱스
    - 희소(sparse) 인덱스

3) 밀집 인덱스

모든 레코드에 대해 [검색키값+포인터] 쌍을 유지

 

4) 희소 인덱스

인덱스의 엔트리가 소수의 검색키 값만을 유지

설명.
검색키값 14001에 해당하는 레코드를 찾으려 한다면 14001보다 작은 값 중에 가장 큰 값을 가진 검색키 값을 찾는다.
14001이 나올 때 까지 다음 값을 순차적으로 읽어들인다.
희소인덱스는 듬성듬성 인덱스를 구성하지만 내부적으로 레코드를 가지고와서 다시 레코드를 찾아봐야한다는 단점이 있지만 인덱스에 해당하는 데이터의 양이 밀집인덱스보다 작기 때문에 레코드가 엄청 큰 릴레이션에서도 비교적 적은 크기의 인덱스 데이터를 가질 수 있다.

5) 다단계 인덱스

밀집 , 희소 인덱스의 장단점을 잘 섞어보자 해서 나온 인덱스

  • 4KB 크기의 블럭에 100개의 엔트리가 삽임될 때, 100,000,000 개(1억개)의 레코드에 대한 순서 인덱스
    - 1,00,000개(백만개)의 블럭 = 4GB의 공간 필요
    (4GB를 메모리에 적재하는건 불가능에 가까움)

  • 인덱스 크기에 따른 검색 성능
    - 인덱스 크기 < 메모리 크기
    디스크 I/O 이 줄어 탐색 시간이 축소
    - 인덱스 크기 > 메모리 크기
    저장된 블럭을 여러번 나누어 읽어야 하기 때문에 디스크 I/O 비용이 증가하여 탐색 시간이 증가

  • 내부 인덱스와 외부 인덱스로 구성
    - 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블럭을 지칭
    - 포인터가 가리키는 블럭을 스캔하여 원하는 레코드보다 작거나 같은 검색키 값 중에 가장 큰 값을 가지는 레코드를 탐색
    (내부 인덱스를 밀집 인덱스에 가깝게 구성하고 내부인덱스 위에 외부 인덱스를 희소인덱스에 가깝게 만들어 여러 층으로 구성되도록 한다.)

  • 내부 인덱스는 1,000,000개의 블럭을 갖고, 외부 인덱스는 100개의 블럭만 사용하여 40MB 크기의 외부 인덱스로 메모리에 적재 가능

 

3. B+ - 트리 인덱스

1) B+ 트리의 원형

2) B+ 트리의 구조

  • 루트 노드로 부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
    - 순서 인덱스(밀집인덱스)는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
    - 현재까지도 널리 사용되는 대표적인 순서 인덱스

  • B+ 트리의 노드 구조

하나의 노드의 사이즈가 일반적인 블럭 사이즈로 구성되고 여러 개의 검색키가 노드 안에 존재한다. K1 ~ Kn개의 검색 키가 있고 P1포인터를 따라가면 K1의 검색키보다 숫자가 작은것 혹은 알파벳이 앞선 것만 있고 P2는 K1과 K2사이의 순서에 존재하는 검색키의 존재만 위치하는 식으로 구성되어있다.

3) B+트리의 구성 요소

  • 인덱스 세트: 루트노드와 중간노드로 구성
    - 단말노드에 있는 검색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용
    - [n/2] ~ n 사이의 개수를 자식으로 소유
    (원하는 레코드가 어디에 있는지 찾기 위해서 힌트를 제공한다 즉, 인덱스세트에는 원하는 레코드가 어디에 가면 찾을 수 있는지 힌트만 제공하는 역할을 한다.) 

  • 순차 세트: 단말노드로 구성
    - 모든 노드가 순차적으로 서로 연결

    (B+트리는 인덱스 세트와 순차 세트로 구성되어있다.)

4) 단말노드의 예

 

5) B+ 트리의 예

단말노드에 포인터는 실제 레코드가 디스크에 어디에 있는지 가리키는 포인터다.

 

6) B+트리의 특징 (외우지않아도 된다. 참고사항일 뿐)

  • 루트는 2, 혹은 [n/2] ~ n 개 사이의 포인터를 가짐

  • 루트와 단말 노드를 제외한 모든 노드는 최소 [n/2]에서 n개 사이의 포인터를 가짐

  • 모든 단말 노드는 루트로부터 같은 거리
    (높이균형트리이기때문)

  • 단말 노드가 아닌 노드에 있는 검색키 값의 수는 그 (중간)노드의 포인터 수보다 하나 작음

  • 단말 노드는 데이터 파일의 순차 세트를 나타내며 모두 리스트로 연결

  • 단말 노드는 적어도 [(n-1)/2] 개의 검색키 값을 포함

 

7) '장보고' 검색

B+트리의 인덱스 첫번째 블럭만 읽어 온다. 정도전보다 크면 오른쪽 작으면 왼쪽으로 가도록 한다.
장보고는 정도전보다 가나다 순에서 작은 범위이므로 왼쪽.
정도전의 왼쪽 포인터를 따라가서 해당 블럭을 가져온다.
'안창호'의 ㅇ 보다 '장보고'의 ㅈ 이 가나다순에서 더 크므로 오른쪽 포인터의 블럭을 디스크에서 읽어온다.
불러온 블럭을 장보고와 같은 검색키값이 있는지 하나씩 비교한 다음 '장보고' 검색키값이 일치하면 왼쪽 포인터에 해당하는 레코드를 읽어온다.

네 번 만에 장보고 레코드를 읽어 올 수 있었다. (겁나 빠름)

 

8) B+ 트리 상에서의 삽입, 삭제(유지비용)

  • 레코드 삽입, 삭제 시 B+트리 또한 수정
    - 레코드 삽입: 노드에서 유지해야 할 검색키 값과 포인터 수 증가로 인해 노드를 분할해야 하는 경우가 발생
    - 레코드 삭제: 노드에서 유지해야 할 검색키 값과 포인터 수 감소로 인해 노드를 병합해야 하는 경우가 발생
    - 높이 균형 유지: 노드가 분할되거나 병합되면서 높이의 균형이 깨지는 경우가 발생

9) B+트리 상에서의 삽입과 삭제

  • 삽입: 검색과 같은 방법을 사용하여 삽입되는 레코드의 검색키 값이 속할 단말 노드를 탐색
    - 해당 단말 노드에 <검색키, 포인터> 쌍을 삽입
    - 삽입 시 검색키가 순서를 유지

  • 삭제: 삭제될 레코드의 검색키를 통해 삭제될 검색키와 포인터를 포함한 단말 노드를 탐색
    - 같은 검색키값을 가지는 다중 엔트리가 존재할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말 노드에서 제거
    - 단말 노드에서 제거된 엔트리의 오른 쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동

10) 노드가 분할되는 삽입

  • '강감찬' 삽입

삽입하기위해 '강감찬'이 들어가야 할 위치를 검색한다. 이 때 검색은 위에 '장보고'를 검색했을 때와 동일한 방법으로 검색한다.
'김영희' '나태양' '도철수'가 있는 블럭에 삽입되어야한다.
하지만 해당 블럭은 꽉 차 있어 들어갈 수 없으므로 분할 해야 한다.
'강감찬'과 '김영희'를 하나의 단말 노드로 구성하고 '나태양'과 '도철수'를 하나의 단말 노드로 구성시킨다.

(빈 공간이 있으면 그냥 넣으면된다.)
노드가 분할이 되면 단말노드가 하나였던것이 두 개가 되므로 부모 노드(중간 노드)에 새로운 포인터를 추가로 삽입해줘야 한다.

▼ 부모 노드(중간노드) 변경 후 ▼

11) 노드가 병합되는 삭제

  • '강감찬'이 추가된 B+트리에서 피천득 삭제
    - 피천득이 있는 단말 노드를 검색
    해당 단말 노드는 삭제 후 홍길동만 남게 됨
    [(n-1)/2] 개 보다 적은 검색키 값이 적으므로 다른 노드와의 병합이 필요

    - 홍길동이 저장 된 노드의 왼쪽의 형제 노드와 병합
    홍길동을 포함한 엔트리를 형제 노드로 이동
    비워진 노드를 삭제
    비워진 노드를 가리키는 포인터도 삭제
    기존의 포인터를 대체할 '정도전'을 부모 노드에 삽입