DB의 Index(인덱스)

* 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조

즉. index는 데이터의 주소값을 저장하는 별도의 특별한 자료구조이다. index를 활용해서 빠르게 원하는 데이터 검색 가능.

1. DB 테이블에 인덱스(index)가 필요한 이유.

 

 a. 만약 table에 index를 걸지 않으면 어떻게 될까?

SELECT *
FROM cutomer
WHERE first_name = "Lee"

- 원하는 데이터를 찾고 싶을 때 table 전체를 full scan 해야함.

- full scan : row를 하나하나씩 모두 확인하는 것을 의미

- 시간 복잡도 : O(N)

 

b. 만약 index가 걸려있다면?

 - 시간 복잡도 : O(logN) B-Tree 기반.

index 자료구조 에서는 추후 기술 예정.

 

* index를 쓰는 이유

 - 조건을 만족하는 튜플들을 빠르게 조회하기 위해서.

 - 빠르게 정렬 (order by) 하거나 그룹핑(group by)하기 위해서.

 

[ 인덱스 설정 : MySQL ]

 

1. 이미 테이블과 데이터가 존재하는 경우 

다음과 같은 테이블이 있다고 가정하자.

CREATE TABLE PLAYER {
	id INT PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    team_id INT NOT NULL,
    back_number INT NOT NULL
};

 

그리고 다음과 같은 두 가지 쿼리문이 있다.

 

SELECT * FROM player WHERE name = "Sonny";
SELECT * FROM player WHERE team_id = 105 and back_number = 7;

 

이때 이렇게 index를 생성할 수 있다.

두 번째 쿼리문 index는 player 테이블에 각 데이터를 유니크하게 식별할 수 있어 UNIQUE INDEX로 생성했다.

 

[Multi Column Index]

 

1) 고려 사항

위의 예시에서 multi column index를 생성했다.

 

CREATE UNIQUE INDEX team_id_back_number_idx ON player (team_id, back_number);

 

? 어떤 경우에 multi column index 생성을 고려해야 할까.

? 어떻게 정렬될까.

? 만약 WHERE back_number=8 조건문이 들어오면 성능은 어떨까.

 

2) 장점 : Convering Index.

위의 예시처럼 INDEX(team_id, back_number) 이 걸려있다. 이때 다음과 같은 쿼리가 들어온다.

 

SELECT team_id, back_number FROM player WHERE team_id = 5;

 

 - 모든 Attribute를 가져오는 것이 아니라 team_id, back_number 두 가지 정보만 가지고 온다.

그러면 인덱스에서 검색한 이후 물리적인 데이터 블록을 읽을 필요가 없다.

 

정리하면,

 - 조회하는 attribute(s)를 index가 모두 cover할 때

 - 조회 성능이 더 빠르다.

 

* Index 구조

 

[Single-Level Ordered Indexes]

 - 각 엔트리는 <탐색 키, 레코드에 대한 포인터>

 - 엔트리들은 탐색 키 값의 오름차순의 정렬

 

1. Primary index (기본 인덱스) | sparse index

 - 탐색 키 값에 따라 정렬된 데이터 파일에 대해 정의

 - 탐색 키가 테이블의 기본 키 (primary key)인 인덱스

 

Dense index : 모든 key value에 대해 index entry를 준다. 즉, 모든 레코드에 대해 색인을 만든다.

Sparse index : 몇몇 값에 대해서만 entry를 만든다. 대부분 기본적으로 sparse index를 사용한다. Primary index도 sparse index 임.

 

2. Clustering indx (클러스터링 인덱스) | sparse index

 - 탐색 키 값에 따라 정렬된 데이터 파일에 대해 정의

 - 많은 레코드가 ordering field에 대한 공통된 값을 가질 경우 사용할 수 있다.

 

3. Secondary index (보조 인덱스) | dense index

 - 다른 인덱스를 돕는 보조 인덱스이며 레코드가 어디 위치한지만 알려주는 역할

 - 주키가 아니라 보조 키를 이용하여 추가적인 방법으로 원하는 값을 가져올 수 있다.

 

[Multi-leval Indexes]

 

 - 인덱스 자체가 큰 경우 인덱스를 탐색하는 시간도 오래 걸릴 수 있다.

 - 인덱스 엔트리를 탐색하는 시간을 줄이기 위해서 Single-Level Ordered Indexes를 디스크 상의 하나의 순서 파일로 생각하고, 이것에 대해 다시 인덱스를 정의할 수 있다.

 - 가장 상위 단계 인덱스를 마스터 인덱스(master index)

 - 대부분은 B+트리를 사용함.

* 동작 방식 (자료 구조)

 - DB index에 자주 쓰이는 자료구조는 B-Tree, B+Tree, Hash Table 이다.

 

* B-tree

시간 복잡도 : O(logN)

 - B-Tree란 자식 노드가 2개 이상인 트리

 - 균형 트리(Balanced Tree) 로서, 최상위 루트 노드에서 리프 노드까지의 거리가 모두 동일

 

* B+tree

 - B+Tree는 B-Tree를 확장 및 개선한 자료 구조

 - 데이터의 빠르접근을 위한 인덱스 역할만 하는 비단말 노드 (Not Leaf)가 분리되어 있다.

 - 관계형 DB에서 가장 많이 사용한다.

 

 

* Hash Table

시간 복잡도 : O(1)

- 위에 살펴본 B-Tree 보다 빠른 결과를 도출할 수 있다. 그런데 왜 B-Tree를 사용할까?

 

[단점]

 - Hash는 등호(=) 연산에만 특화되어 있어 부등호 연산(>,<)이 자주 사용되는 데이터베이스 검색에는 해시 테이블이 적합하지 않다.

즉. equality 비교만 가능하고 range 비교는 불가능하다.

 - multi column index의 경우, 전체 attributes에 대한 조회만 가능하다.

  1. 예를 들어, 위의 B-Tree 기반의 인덱스에서는 INDEX(team_id, back_number)는 상황에 따라 team_id 칼럼만으로 조회를 할 수 있다.

  2. 하지만 hash index는 무조건 두 칼럼 모두 사용해서 조회해야 한다.

 

* 왜 Index로 B tree 계열이 사용될까

[Secondary storage (SSD or HDD)]

- 데이터를 처리하는 속도가 가장 느리다

- 디스크 I/O가 많이 발생하면 느림.

- 데이터를 저장하는 용량이 가장 크다.

- block 단위로 데이터를 읽고 쓴다.

 

이때 DB는 secondary storage에 저장된다.

위의 특징을 고려했을때 DB에서 데이터를 조회할때 secondary storage에 최대한 적게 접근하는 것이 성능 면에서 좋다.

또한 block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있다.

 

* 정리

- secondary storage에 최대한 적게 접근하는것이 좋다.

- B-트리를 사용하면 다른트리 (Binary Tree, RB Tree)보다 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있다.

- 또한 B-트리 노드는 여러 개의 데이터를 저장할 수 있다. ( = 여러 개의 자녀 노드를 가짐 )