[CS스터디] Index

--목차--

Index?

Index 자료구조

Primary Index vs Secondary Index

Composite Index

Index의 성능과 고려해야 할 사항

--------

 

 

 

 

 

1. Index?

1) 정의

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

칼럼의 값-해당 레코드가 저장된 주소를 키와 값의 쌍으로 이루어졌다.

 

2) 목적

DMBS가 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸리기 때문에 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스 생성해서 원하는 데이터를 빠르게 갖고 오기 위함.

 

3) 특징

• 인덱스를 사용하지 않을 경우, Full Scan(전체탐색)을 해야 하는데 전체를 비교하기 때문에 처리 속도 효율이 좋지 않음.
• DBMS의 인덱스는 데이터의 저장 성능을 희생하고 데이터의 읽기 속도를 높이는 기능.
• 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는데는 빠르지만 새로운 값을 추가, 삭제, 수정하는 경우 오버헤드가 발생하여 쿼리문 실행 속도가 느려진다.
• ex) SELECT 쿼리 문장의 WHERE 조건절에 사용되는 컬럼이어서 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져 역효과를 불러온다.
• 데이터를 오름차순으로 정렬하여 정렬된 주소체계라고 말할 수 있다.

 

4) 장단점

• 장점
  • 테이블을 조회하는 속도와 성능 향상
    • 조건 검색 WHERE절의 효율성(이미 데이터가 정렬되어 있어 해당 조건에 맞는 데이터를 빠르게 찾아낼 수 있음.)
    • 정렬 ORDER BY절의 효율성(ORDER BY는 정렬 과정이어서 부하가 많이 필요하지만 하지 않아도 됨.)
      • 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생하기 때문
    • MIN, MAX 효율적 처리 가능
  • 전반적인 시스템의 부하 감소

 

• 단점
  • 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장 공간 필요. (속도 향상과 단점의 정도를 비교하고 결정해야 함.)
  • 인덱스 관리를 위한 추가 작업 필요. (INDEX 테이블, 원본 테이블 둘 다 수정 작업을 해야 함.)
  • 인덱스를 잘못 사용할 경우 오히려 성능 저하되는 역효과 발생.
    • (CREATE, DELETE, UPDATE(DML) 빈번한 속성에 인덱스를 걸면 인덱스의 크기가 비대해져 성능 저하.
    • UPDATE, DELETE : 기존 인덱스를 삭제하지 않고 사용하지 않음 처리를 하기 때문)
  • 테이블의 전체 데이터 중 10~15% 이하의 데이터를 처리하는 경우만 효율적이고 그 이상의 데이터 처리시 인덱스를 사용하지 않는 것이 더 효율적.

 

5) 기타 정보

• 옵티마이저
  • 가장 효율적인 방법으로 SQL을 수행할 최적의 처리 경로를 생성하는 DBMS의 핵심 엔진.
  • 특정 컬럼에 인덱스 생성 시, 해당 컬럼 데이터들을 정렬해 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장.
  • 인덱스 생성 시 쿼리문에서 WHERE 조건을 거는 것과 같은 작업을 수행.
• DBMS에 성능 문제 발생 시 Index를 남발하면 안되는 이유
  • Index가 쌓여가는 것은 하나의 쿼리문을 빠르게 만들 수 있지만, 전체적으로 INSERT, UPDATE, DELETE 부하가 증가해 전체적인 데이터베이스 성능 저하 발생.
  • 인덱스보다 SQL문을 효율적으로 짜야 함.

 

 

 

2. Index 자료구조

1) B+ Tree 인덱스 알고리즘

• 칼럼의 값을 변형하지 않고 값의 앞부분만 잘라서 관리.
• 원래의 값을 이용해 인덱싱.
• 일반적으로 사용되는 알고리즘.
• 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조.
  • 부등호를 이용한 순차 검색 연산이 자주 발생하여서 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화.
• SELECT 질의 조건에는 부등호 연산도 포함이 되므로 hash table사용시 등호 연산이 아닌 부등호 연산시 문제 발생.
• (동등 연산에 특화된 hash table은 데이터베이스 자료구조로 적합하지 않음.)
• ++ B+Tree와 BTree의 차이
  • 리프노드(데이터 노드)만 인덱스와 함께 데이터(Value)를 갖고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
  • 리프노드들은 Linked List로 연결되어 있다.
  • 데이터 노드 크기는 인덱스 노드 크기와 같지 않아도 된다.
• 시간복잡도 O(logn)

 

 

2) Hash 인덱스 알고리즘

• 칼럼의 값으로 해시 값을 계산해서 인덱싱.
• 값을 변형해서 인덱싱.
• 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다.
• (전방일치 : 특정 문자로 시작하는 값으로 검색하는 것)
• 메모리 기반 데이터베이스에서 많이 사용.
• 시간복잡도 O(1)

 

3) 기타

R-Tree, Fractal-Tree, Merge-Tree

 

 

 

3. Primary Index vs Secondary Index

1) Clustered Index?

• 프라이머리 키 값이 비슷한 레코드끼리 묶어서 저장하는 형태로 구현.
• 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안.
• (물리적으로 인접한 장소에 저장되어 있는 데이터)
• 테이블의 프라이머리 키에서만 적용되는 내용.
• 프라이머리 키를 신중하게 결정하고 클러스터드 인덱스를 사용해야 함.
• 프라이머리 키 값이 변경되면 레코드의 물리적 저장 위치또한 변경되어야 함.
• 테이블 당 1개만 생성 가능. (프라이머리 키에 대해서만 적용되어서)
• non 클러스터드 인덱스는 테이블 당 여러 개 생성 가능.

2) Index 종류

https://brunch.co.kr/@skeks463/25 참조

 

 

4. Composite Index

SELECT 질의를 어떻게 할 것인가가 인덱스를 어떻게 생성할 것인가에 대해 많은 영향 끼침.

(인덱스를 설정하는 필드의 속성 중요.)

 

 

 

5. Index의 성능과 고려해야 할 사항.

1) Index가 항상 좋은 것일까?

• Index 생성시 INSERT, DELETE, UPDATE 쿼리문 실행시 별도의 과정 추가적으로 발생.
• INSERT : Index 데이터를 추가해야 하므로 성능에 손실 발생.
• DELETE : Index에 존재하는 값은 삭제하지 않고 사용 안한다는 표시로 남게 됨.
• row의 수는 그대로이므로 실제 데이터보다 더 많은 데이터가 존재한다는 결과 발생.
• index의 본질을 잃게 됨.
• UPDATE :  INSERT, DELETE 문제점 동시 수반. (이전 데이터가 사라지고 그 자리에 새 데이터가 들어오기 때문에 변경 전 데이터는 삭제되지 않고 INSERT로 인한 split도 발생.)

 

-> 데이터의 형식에 따라 인덱스 생성의 효율이 결정됨. 사용하지 않는 인덱스는 바로 제거를 해야 함.

 

2) Index를 사용하면 좋은 경우

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• JOIN / WHERE / ORDER BY에 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼.

3) Index 생성 전략

데이터의 분포도는 최대한, 조건절 호출 빈도는 자주 사용되는 컬럼을 인덱스로 생성하는 것이 좋음.

기준 컬럼은 최대한 중복이 되지 않는 값.(특정 컬럼을 기준으로 생성하고 기준이 된 컬럼으로 정렬된 인덱스 테이블이 생성되기 때문)

PK로 인덱스 거는 것이 베스트.

• 조건절에 자주 등장하는 컬럼
• 항상 등호로 비교되는 컬럼
• 중복되는 데이터가 최소한인 컬럼(분포도가 좋은 컬럼, Cardinality(특정 데이터 집합의 유니크한 값의 수)가 높은 컬럼)
• ORDER BY 절에서 자주 사용되는 컬럼
• JOIN 조건으로 자주 사용되는 컬럼

 

 

 

 

 

 

참조

https://brunch.co.kr/@skeks463/25

https://steady-coding.tistory.com/536

https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/

https://choicode.tistory.com/27

https://mangkyu.tistory.com/96

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database#index

GitHub - JaeYeopHan/Interview_Question_for_Beginner: Technical-Interview guidelines written for those who started studying progr