인덱스(index)

‘색인’이라고도 불리는 인덱스는 데이터베이스 객체 중 하나이다.

• 테이블에는 인덱스를 작성할 수 있다.

 

 

1. 인덱스

인덱스의 역활은 검색속도의 향상이다.

• ‘검색(혹은 탐색)’이란 SELECT 명령에 WHERE 구로 조건을 지정하기도 하고 그에 일치하는 행을 찾는 일련의 과정을 말한다.
• 테이블에 인덱스가 지정되어 있으면 효율적으로 검색할 수 있어 WHERE로 조건이 지정된 SELECT 명령의 처리 속도가 향상된다.

쉽게 생각하면 책 안에 있는 특정한 부분을 찾고 싶은 경우, 본문을 처음부터 읽어나가기보다 
목차나 색인을 참고해서 찾는 편이 효율적인데 인덱스가 이런 역활을 한다.

• 데이터베이스의 인덱스에는 검색 시에 쓰이는 키워드와 대응하는 데이터 행의 장소가 지정되어 있다.

인덱스는 테이블과는 별개로 독립된 데이터베이스 객체로 작성된다.

• 목차밖에 없는 책은 본적이 없는 것처럼 인덱스만으로는 아무런 의미가 없다.

인덱스는 테이블에 의존하는 객체라고 할 수 있다.
대부분의 데이터베이스에서는 테이블을 삭제하면 인덱스도 같이 삭제된다.

---

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

• 데이터 탐색, 검색 알고리즘 등

인덱스를 사용하면 효율적으로 검색할 수 있는 이유?

데이터베이스의 인덱스에 쓰이는 대표적인 검색 알고리즘은 ‘이진 트리(binary tree)’가 있다.

• 그 다음으로 ‘해시’가 유명하다.

이진 트리는 정확히 말하면 탐색 방법이라기 보다는 데이터 구조에 가깝다.

• 탐색 방법으로 말하면 ‘이진 탐색(binary search)’
  • 이진탐색에서 검색하기 쉬운 고조로 한 것이 이진 트리이다.

풀 테이블 스캔(full table scan)

인덱스가 지정되지 않은 테이블을 검색할 떄는 풀 테이블 스캔이라 불리는 검색 방법을 사용한다.

• 테이블에 저장된 모든 값을 처음부터 차례로 조사해나간다.
  • 아주 단순한 검색방법으로, 행이 1,000건 이라면 최대 1,000번 값을 비교한다.

이진 탐색(binary search)

이진 탐색은 차례로 나열된 집합에 대해 유효한 검색 방법이다.

• 처음부터 순서대로 조사하는 것이 아니고 집합을 반으로 나누어 조사하는 검색방법이다.
• 고속으로 검색할 수 있는 탐색 방법이지만 데이터가 미리 정렬되어 있어야 한다.
  • 테이블 내의 행을 언제나 정렬된 상태로 두는 것은 힘든 작업이다.

실제로 테이블의 행과 같이 세로로 나열되어 있다고 생각하자.

1

2

3

5

10

11

19

20

23

30

31

32

38

40

100

차례로 나열된 수치의 집합에서 ‘30’을 검색한다고 했을 때

• 열이름 no라고 하고 WHERE no = 30과 같은 조건을 지정한다면+
  • 15개의 수치 데이터에서 30의 위치를 찾으려고 한다.

이진 탐색에서는 집합의 가운데에서부터 조사하기 시작한다. (가운데 값은 20)

• 정렬이 되어있는 상태에서 30이라는 값은 20보다 큰 오른쪽 값들만 있으면 될 것이다.

23

30

31

32

38

40

100

여기서 다시 가운데를 기준으로 30 < 32(가운데 값)이므로 이번에는 왼쪽에 원하는 수치가 있을 것이다.

23

30

31

가운데 값이 30이기 때문에 총 세 번 비교해 목표를 찾을 수 있다.

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

지금 사례는 데이터수가 15개에 불과해 풀 테이블 스캔이나 이진 탐색이나 크게 차이가 없을 수 있다.

• 이진 탐색은 데이터 수가 배가 되어도 비교 횟수는 1회밖에 늘어나지 않는다.

실제 데이터베이스에는 수만, 수천만 건의 행이 있으므로 대량의 테이터를 검색할 때는 이진 탐색이 빠르다.

-이진 트리(binary tree)

일반적으로 테이블에 인덱스를 작성하면 테이블 데이터와 별개로 인덱스용 데이터가 저장장치에 만들어진다.

• 이때 이진 트리 데이터 구조로 작성된다.

생성 예시 참조

 

[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)

 

50

15

62

70

7

54

11

1. 50을 트리의 루트로 트리에 삽입합니다.
2. 다음 요소를 읽고 루트 노드 요소보다 작 으면 왼쪽 하위 트리의 루트로 삽입합니다.
3. 그렇지 않으면 오른쪽 하위 트리의 오른쪽 루트로 삽입합니다.

이진 탐색의 예로 사용했던 집합을 그래도 이진 트리로 구조로 만들어 봤을 때

트리는 노드(node)라는 요소로 구성된다. (각 노드는 두 개의 가지로 나뉘어져 있다.)

• 노드의 왼쪽 가지는 작은 값, 오른쪽 가지는 큰 값으로 나뉘어져 있다. (두 개의 가지로 분기하는 구조)

10이라는 값을 검색한다고 했을 때

• 이진 탐색에서는 가운데 값부터 검색하기 시작했지만 이진 트리의 경우에는 트리의 루트 노드부터 시작한다.
  • 최상단에 20이라는 값으로 된 루트 노트부터 검색을 시작한다.
• 검색의 진행 방법은 이진 탐색과 거의 비슷하다.
  • 원하는 수치와 비교해서 더 크면 오른쪽 가지를, 작으면 왼쪽 가지를 조사해 나간다.
  • 이진 탐색의 경우는 오른쪽의 가운데, 왼쪽에 가운데 값을 계산해야 하지만, 이진 트리에서는 구조 자체가 검색하기 쉬우므로 가지를 따라 이동하기만 하면 된다.

1.  20 > 10 이기 때문에 우선은 왼쪽 가지로 이동
2.  5 < 10 이므로 이번에는 오른쪽 가지로
3.  11 > 10 이므로 이번에는 왼쪽으로 간다.

3번만에 원하는 값인 10을 찾았다.

---

3. 유일성 (이진 트리에는 중복하는 값을 등록할 수 없다.)

이진 트리의 주로를 보면, 같은 값을 가지는 노드가 여러 개 있을 때의 결과에 대한 의문이 생길 수 있다.

• 이진 트리에서는 집합 내에 중복하는 값을 가질 수 없다.
• 큰 쪽과 작은 쪽의 두 가지로 나뉘며 2가지의 가지만 필요하다.
  • 값을 허용하기 위해서는 > < 등호만 필요하며 = ’같은’ 이라는 제 3의 가지를 가질 필요가 있다.

인덱스 작성과 삭제

테이블에 인덱스를 작성하는 방법

CREATE INDEX
DROP INDEX

• 인덱스는 데이터베이스 객체의 하나로 DDL을 작성하거나 삭제한다.
  • 표준 SQL에는 CREATE INDEX 명령은 없다.

인덱스 자체가 데이터베이스 제품에 의존하는 선택적인 항목으로 취급된다.

• 대표적인 데이터베이스 제품에는 모두 인덱스 구조가 도입되어 있으며, 모두 비슷한 방법으로 인덱스를 다룰 수 있다.

---

인덱스 작성

 

인덱스는 CREATE INDEX 명령으로 만든다.

인덱스에 이름을 붙여 관리하는데. 데이터베이스 객체가 될지 테이블의 열처럼 취급될지는 데이터베이스 제품에 따라 다르다.

• Oracle이나 DB2 등에서 인덱스는 스키마 객체가 된다.
  • 스키마 내에 이름이 중복하지 않도록 지정해 관리한다.
• SQL Server나 MySQL에서 인덱스는 테이블 내의 객체가 된다.
  • 테이블 내에 이름이 중복되지 않도록 지정해 관리한다.

인덱스를 작성할 때는 해당 인덱스가가 어느 테이블의 어느 열에 관한 것인지 지정해야 한다.

• 열은 복수로도 지정할 수 있다.
  • 인덱스의 네임스페이스가 데이터베이스 제품마다 다르다는 점 주의하기

CREATE INDEX 인덱스명 ON 테이블명 (열명1,열명2,...)

• 인덱스를 작성할 때는 저장장치에 색인용 데이터가 만들어진다.

테이블 크기에 따라 인덱스 작성시간도 달라지는데, 행이 대량으로 존재하면 시간도 많이 걸리고
저장공간도 많이 소비한다.

작성한 인덱스의 열을 WHERE구로 조건을 지정하여 SELECT 명령으로 검색하면 처리속도가 향상된다.

• 모든 SELECT 명령에 적용되는 만능 인덱스는 작성할 수 없다.
• INSERT 명령의 경우 인덱스를 최신 상태로 갱신하는 처리가 늘어나므로 처리속도가 조금 떨어진다.

인덱스를 작성했다고 가정했을 때

CREATE INDEX indexExam ON tableExam(a);

WHERE 구에 a 열에 대한 조건식을 지정한 경우 SELECT 명령은 인덱스를 사용해 빠르게 검색할 수 있다.

• SELECT * FROM tableExam WHERE a = ‘a’;
• WHERE 구의 조건식에 a 열이 전혀 사용되지 않으면 SELECT 명령은 indexExam라는 인덱스를 사용할 수 없다.

인덱스 삭제

인덱스는 DROP INDEX 명령으로 삭제한다.

DROP 할 때는 다른 객체와 동일하게 인덱스 이름만 지정하면 된다.

• 테이블 내 객체로서 작성하는 경우에는 테이블 이름도 지정해야 한다.
  • 이 때 인덱스를 구성하는 열은 지정할 필요가 없다.

DROP INDEX 인덱스명

• 스키마 객체의 경우

DROP INDEX 인덱스명 ON 테이블명

• 테이블 내 객체의 경우

인덱스는 테이블에 의존하는 객체이다.

• DROP TABLE로 테이블을 삭제하면 테이블에 작성된 인덱스도 자동으로 삭제된다.
• 인덱스만 삭제하는 경우에는 DROP INDEX를 사용한다.

1. EXPLAIN

인덱스 작성을 통해 쿼리의 성능 향상을 기대할 수 있다.

• 이때 실제로 인덱스를 사용해 검색하는지를 확인하려면 EXPLAIN 명령을 사용한다.

EXPLAIN SQL 명령

• EXPLAIN에 뒤이어 확인하고 싶은 SELECT 명령 등의 SQL 명령을 지정하면 된다.
  • 이 SQL 명령은 실제로 실행되지 않는다!! (주의하기)
  • 어떤 상태로 실행되는지를 데이터베이스가 설명해줄 뿐이다.
    • MySQL의 경우 상황에 따라 다르지만 필요한 정보를 얻기 위해 SQL 명령의 일부분을 실제로 실행하는 경우도 있다.

EXPLAIN은 표준 SQL에는 존재하지 않는다.

• 데이터베이스 제품 의존형 명령이다. (어떤 데이터베이스 제품이라도 이와 비슷한 명령을 지원한다.)

EXPLAIN SELECT * FROM tableExam WHERE a = 'a';

 

id	select_type	table	type	possible_keys	key
1	SIMPLE	tableExam	ref	indexExam	indexExam

• tableExam의 a 열에는 indexExam이라는 인덱스가 작성되어 있다.
  • EXPLAIN의 뒤를 잇는 SELECT 명령은 a 열의 값을 참조해 검색하므로 indexExam을 사용해 검색한다.
  • possible_keys 라는 곳에 사용될 수 있는 인덱스가 표시되며, key는 사용된 인덱스가가 표시된다.

WHERE 조건을 바꾼다면?

EXPLAIN SELECT * FROM tableExam WHERE no > 10;

id	select_type	table	type	possible_keys	key
1	SIMPLE	tableExam	ALL	NULL	NULL

a 열을 사용하지 않도록 조건을 변경하면 인덱스를 사용할 수 없어 possible_keys와 key가 NULL이 되었다.

 

---

4. 최적화

SELECT 명령을 실행할 때 인덱스의 사용 여부를 선택한다.

• 데이터베이스 내부의 최적화에 의해 처리되는 부분이다.

내부 처리에서는 SELECT 명령을 실행하기에 앞서 실행계획을 세운다.

• 실행계획에서는 ‘인덱스가 지정된 열이 WHERE 조건으로 지정되어 있으니 인덱스를 사용하자’와 같은 처리가 이루어진다. (EXPLAIN 명령은 이 실행계획을 확인하는 명령)

실행계획에서는 인덱스의 유무뿐만 아니라 인덱스를 사용할 것인지 여부에 대해서도 데이터베이스 내부의 최적화 처리를 통해 판단한다. 

• 이때 판단 기준으로 인덱스의 품질도 고려한다.
• ‘예’ 또는 ‘아니오’라는 값만 가지는 열이 있다면, 해당 열에 인덱스를 지정해도 다음과 같은 이진트리가 되어 좋은 구조를 가지지 못한다.

단순한 리스트와 별다른 차이가 없는 구조이다.

• 극단적인 사례이지만 이진탐색에 의한 효율화를 기대할 수 없다.
• 데이터의 종류가 적으면 적을수록 인덱스의 효율도 떨어진다.
  • 반대로 서로 다른 값으로 여러 종류의 데이터가 존재하면 그만큼 효율은 좋아진다.

이런식으로 인덱스의 품질을 고려해 실행계획이 세워진다.

---

다음에 보기

[SQL] 인덱스(Index)을 알아야 정확한 실행계획을 알수있다

 

[DB] 데이터베이스 실행 계획에 대하여

 

SQL) 001. SQL 인덱스(Index)의 종류와 각 Index Scan 방식의 특징

 

다양한 인덱스 스캔 방식,. - [종료]구루비 DB 스터디 - 개발자, DBA가 함께 만들어가는 구루비 지식