[데이터베이스] - 인덱스

인덱스란?

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

즉, index란 데이터의 주소값을 저장하는 별도의 특별한 자료 구조이다. index를 활용해서 빠르게 원하는 데이터를 찾을 수 있다.

 

 

- DB테이블에 인덱스가 필요한 이유

• 원하는 데이터를 찾고 싶을 때 테이블 전체를 풀스캔(full scan) 해야 한다.
• Full Scan 시간 복잡도 : O(N)
• Index를 사용한 경우 시간 복잡도(B tree) : O(logN)

 

- 인덱스를 사용하는 이유

• 조건에 만족하는 튜플(들)을 빠르게 조회하기 위해서
• 빠르게 정렬(order by)하거나 그룹핑(group by) 하기 위해

 

- 인덱스 설정하는 방법

 

- 이미 테이블과 데이터가 존재할 경우

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;

 

아래는 테이블과 쿼리문이 있을때 인덱스를 생성하는 방법이다.

-- single column index
CREATE INDEX player_name_idx ON player(name);

-- multi column index
CREATE UNIQUE INDEX team_id_back_number_idx ON player(team_id, back_number);

 

 

- 테이블 생성시 Index 생성

CREATE TABLE PLAYER(
    id INT PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    team_id INT NOT NULL,
    back_number INT NOT NULL,
    INDEX player_name_idx(name),
    UNIQUE INDEX team_id_back_number_idx(team_id, back_number)
);

 

 

 

---

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절에서 AND 연산자에 의해 자주 같이 질의되는 칼럼인 경우
- 한 칼럼에만 인덱스를 생성하였다면 AND 조건에서 인덱스가 아닌 칼럼을 찾는 연산자의 경우엔 풀스캔이다.
- 그러므로 Multi Column Index 설정을 고려해야 한다.

 

🤔 생성할 때 어떤 순서로 정렬되는 걸까?
💡 앞에 오는 순으로 정렬된다. INDEX(a, b)  a부터 정렬

 

🤔 WHERE back_number = 7 조건문이 들어오면 성능은 어떨까?
💡 위의 생성된 Multi Column Index는 우선 team_id를 기준으로 정렬되어 있기 때문에 풀 스캔과 같거나 좋지 않을 수도 있다

 

2) 장점

Covering Index

SELECT team_id, back_number FROM player WHERE team_id = 5;

모든 Attribute를 가져오는 것이 아닌 인덱스로 설정한 정보만 가지고 온다. 그러면 인덱스에서 검색한 이후 물리적인 데이터 블록을 읽을 필요가 없다.

• 조회하는 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 index (클러스터링 인덱스) | sparse index

• 탐색 키 값에 따라 정렬된 데이터 파일에 대해 정의
• 많은 레코드가 ordering field에 대한 공통된 값을 가질 경우 사용할 수 있다.

 

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

• 다른 인덱스를 돕는 보조 인덱스이며 레코드가 어디 위치한 지만 알려주는 역할
• 주키가 아니라 보조 키를 이용하여 추가적인 방법으로 원하는 값을 가져올 수 있다.

Multi-Level Indexes

• 인덱스 자체가 큰 경우 인덱스를 탐색하는 시간도 오래 걸릴 수 있다.
• 인덱스 엔트리를 탐색하는 시간을 줄이기 위해서 Single-Lever Ordered Indexes를 디스크 상의 하나의 순서 파일로 생각하고, 이것에 대해 다시 인덱스를 정의할 수 있다.
• 가장 상위 단계 인덱스를 마스터 인덱스(Master index)
• 대부분은 B+트리를 사용

 

 

 

---

동작 방식 (자료구조)

데이터베이스 인덱스에 자주 쓰이는 자료구조는 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계얼을 사용할까?

✌️Hash Table 단점

• 해시는 등호(=.!=) 연산에만 특화되어 있어 부등호 연산(<, <=)이 자주 사용되는 데이터베이스 검색에는 테이블이 적합하지 않다.
  즉, equality비교만 가능하고 range 비교는 불가능하다.
• Multi Column Index의 경우, 전체 Attributes에 대한 조회만 가능하다.
  B Tree 기반의 인덱스에서는 INDEX(a, b)는 상황에 따라 a칼럼으로 조회가 가능하다.
  하지만, Hash Index는 무조건 두 칼럼 모두 사용해서 조회해야 한다.

 

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

✌️Secondary Storage (SSD or HDD)

• 데이터를 처리하는 속도가 가장 느리다
• 디스크 I/O (특히 랜덤 I/O)가 많이 발생하면 느리다.
• 데이터를 저장하는 용량이 가장 크다.
• Block단위로 데이터를 읽고 쓴다.
  이때 데이터베이스는 Secondary Storage에 저장된다.

위의 특징을 고려했을 때 데이터베이스에서 데이터를 조회할 때 Secondary Storage에 최대한 적게 접근하는 것이 성능면에서 좋다.
(데이터베이스의 I/O는 디스크를 통해 물리적인 작업을 거치기 때문)

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

🗒️정리

• Secondary Storage에 최대한 적게 접근해야 한다.
• B Tree 계열을 사용하면 다른 트리보다 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있다.
• B Tree 노드는 여러 개의 데이터를 저장할 수 있다. ( 여러 개의 자녀 노드를 가질 수 있다.)

 

---

Index를 설정할 때 고려사항

-  성능저하

• 테이블에 witer 작업 (INSERT, DELETE, UPDATE)을 할 때 index도 추가적인 연산이 발생
• 추가적인 저장공간 차지

-  Full scan이 성능이 더 좋은 경우

• full scan을 할지 여부는 optimizer가 판단

-  테이블에 데이터가 조금 있을 때

-  조회하려는 데이터가 테이블의 상당 부분을 차지할 때

보통 전체 데이터의 5~10% 정도로 걸러지는 경우 index를 사용했을 때 좋은 효율을 낼 수 있다.
전체 데이터 20%를 넘어가는 경우에는 full scan이 빠를 수 있다.

 

 

---

인덱스 설정 기준

- Cardinality ( 카디널리티 )

• 카디널리티가 높을수록 인덱스 설정에 좋은 칼럼이다. ( 한 칼럼이 갖고 있는 값의 중복 정도가 낮을수록 좋다.)
• 인덱스를 통해 불필요한 데이터의 대부분은 걸러낼 수 있다.

- Selectivity ( 선택도 )

• 선택도가 낮을수록 인덱스 설정에 좋은 칼럼이다. (일반적으로 5~10% 적당)
• 선택도가 낮다는 의미는 한 칼럼이 갖고 있는 값 하나로 적은 row가 찾아지는 것을 의미한다.

※
선택도 계산법 (전체 레코드 중에서 조건절에 의해 선택되는 레코드 비율)
: 칼럼의 특정 값의 row 수 / 테이블의 총 row 수 * 100

-  활용도

• 활용도가 높을수록 인덱스 설정에 좋은 칼럼이다.

-  수정 빈도

• 수정 빈도가 낮을수록 인덱스 설정에 좋은 칼럼이다.
• 인덱스 설정된 칼럼이 값이 바뀌게 된다면 인덱스도 새로 갱신해주어야 하기 때문이다.

 

출처 : github.com/devSquad-study