[SQL 첫걸음] 6장.데이터베이스 객체 작성과 삭제 - 28.인덱스 구조

저자 : 아사이 아츠시

출판 : 한빛미디어 

발매 : 2015.11.01

1. 인덱스

- 인덱스는 테이블에 붙여진 색인. 인덱스의 역할은 검색속도의 향상.

- 테이블에 인덱스가 지정되어 있으면 효율적으로 검색할 수 있으므로 WHERE로 조건이 지정된 SELECT 명려으이 처리 속도가 향상됨. 

- 책의 목차나 색인이 인덱스와 비슷. 책 안에 있는 특정 부분을 찾을 때 본문을 처음부터 읽어나가기보다 목차나 색인을 참고해서 찾는 편이 효율적. 인덱스가 바로 이런 역할을 함.

인덱스의 구조도 목차나 색인과 비슷. 목차나 색인에 제목ㆍ키워드별 페이지 번호 적혀있듯, 데이터베이스의 인덱스에는 검색 시에 쓰이는 키워드와 대응하는 데이터 행의 장소가 저장되있음.

- 인덱스는 테이블과는 별개로 독립된 데이터베이스 객체로 작성됨. 하지만 인덱스만으론 아무런 의미가 없음. 인덱스는 테이블에 의존하는 객체. 대부분의 데이터베이스에서는 테이블을 삭제하면 인덱스도 같이 삭제됨.  

2. 검색에 사용하는 알고리즘

- 데이터베이스의 인덱스에 쓰이는 대표적인 검색 알고리즘으로는 '이진 트리(binary tree)'가 있으며, 그 다음으로 '해시'가 유명.

cf. 이진 탐색 (binary search) 

 (이진탐색에서 검색하기 쉬운 구조가 이진 트리 데이터 구조) 

- 풀 테이블 스캔 (full table scan) : 인덱스가 지정되지 않은 테이블을 검색할 때는 풀 테이블 스캔 검색 방법 사용. 테이블에 저장된 모든 값을 처음부터 차례로 조사. 행이 1000건 있다면 최대 1000번 값을 비교. 

- 이진 탐색 (binary search) : 이진 탐색은 차례로 나열된 집합에 유효한 검색 방법. 처음부터 순서대로 조사하지 않고 집합을 반으로 나누어 조사하는 검색방법. 

ex) 

1

3

5

10

11

30

32

35

40

45

위와 같이 차례로 나열된 수치 집합에서 30을 검색하고자 할 때,

1 . 이진 탐색에서는 집합의 가운데에서부터 조사를 시작함. 가운데 값은 11 

    검색하려는 30은 11보다 크므로 가운데를 기준으로 오른쪽에 있을것. 그 오른쪽 부분에서 다시 가운데를 기준으로 잡아 조사. 

1

3

5

10

11

30

32

35

40

45

2. 오른쪽의 가운데 값은 35. 30<35 이므로 이번에는 왼쪽에 원하는 수치가 있을 것. 

   가운데 기준으로 왼쪽 부분을 다시 가운데를 기준으로 잡아 조사. 

1

3

5

10

11

30

32

35

40

45

3. 가운데 값은 30으로 마침내 30을 찾음. 

=> 만약 풀 테이블 스캔으로 했다면 6번을 비교해야 했겠지만, 이진 탐색이라면 3회로 끝나기 때문에 더 효율적. 

실제 디비에는 수만,수천만 건의 행이 있음. 풀 테이블 스캔을 한다면 데이터 수에 비례해 비교횟수도 늘어남. 그에 비해 이진 탐색은 데이터 수가 배가 되어도 비교횟수는 1회밖에 늘어나지 않음. 따라서 데량의 데이터를 검색할 때는 이진 탐색이 빠르다!!!

• 이진 트리 (binary tree) 

- 이진 탐색은 고속으로 검색할 수 있는 탐색 방법이지만 데이터가 미리 정렬되어 있어야 함. 하지만 테이블 내의 행을 언제나 정렬된 상태로 두는 것은 힘든 작업. 

일반적으로 테이블에 인덱스를 작성하면 테이블 데이터와 별개로 인덱스용 데이터가 저장장치에 만들어짐. 이때 이진 트리라는 데이터 구조로 작성됨. 

출처 : SQL 첫걸음

- 트리는 노드(node)라는 요소로 구성. 각 노드는 두개의 가지로 나뉨. 노드의 왼쪽 가지는 작은 값으로, 오른쪽 가지는 큰 값으로 나뉘어짐. 두 가지로 분기하는 구조여서 '이진 트리'라 불림. 

- 검색의 진행 방법은 이진 탐새과 거의 비슷. 원하는 수치와 비교해서 더 크면 오른쪽 가지를, 작으면 왼쪽의 가지를 조사. 

- 이진 탐색의 경우는 오른쪽의 가운데, 왼쪽의 가운데 값을 계산해야 하지만, 이진 트리에서는 구조 자체가 검색하기 쉬우므로 가지를 따라 이동하기만 하면 됨.

3. 유일성

- 이진 트리에서는 집합 내에 중복하는 값을 가질 수 없음. 이진 트리에서 같은 값을 가지는 노드를 여러개 만들 수 없다는 특성은 키에 대하여 유일성을 가지게 할 경우에만 유용. 그래서 기본키로 이진 트리 인덱스를 작성하는 데이터베이스가 많음.