ETC.

CS/데이터베이스

인덱스란 ?

이-프 2023. 8. 23. 19:16

인덱스란?

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

왜 Index를 사용하는가?

  • 특정 기준(Where구문과 일치하는) 맞는 rows를 빠르게 찾기 위해서 사용

    └ Table의 컬럼을 색인화(따로 파일로 저장)하여 검색시, 해당 Table의 데이터를 Full-Scan하지 않고, 인덱스 파일만을 검색하여 검색 속도를 up

  • 특정 열을 고려 대상에서 빨리 없애기 위해
  • Join을 실행할 때, 다른 테이블에서 열을 추출하기 위해
  • 쿼리를 최적화하는 경우

Index의 장단점

  • 장점
    • 키 값을 기초로 하여 검색과 정렬 속도를 향상
    • 그룹화 작업의 속도를 향상
    • 테이블 행의 고유성을 강화
    • 테이블의 pk는 자동으로 인덱스가 됨
  • 단점
    • 인덱스를 관리하는 비용 발생
    • 인덱스를 저장하기 위한 space 사용 증가
    • 만약 index를 쓰지 않는다면 ? Full Scan을 수행해야함 = 처리 속도 매우 느려짐
    • 데이터 변경 작업이 자주 일어날 경우, 계속해서 재작성해아 하므로, 성능에 오히려 악영향

      └ 데이터 변경 ,추가, 삭제 == 성능 악화

💡
그럼 Index를 자주 쓰면 된다/안된다 ?

정답은 No. 남발하면 안된다.

DB 서버에 성능 문제가 발생하면 가장 빨리 해결할 수 있는 방법은 인덱스 추가이다.

계속해서 인덱스를 생성하게 되면, 하나의 쿼리문을 빠르게 만들수는 있지만, 전반적으로 봤을 때 데이터베이스의 성능을 악화시키는 꼴이다.

구체적으로, 조회 성능을 극대화하려고 인덱스를 쓰는 건데, 오히려 Insert, Delete, Update 하는 시간이 오래 걸려서 db 조회가 오래 걸리는 문제가 발생할 수 있는 것이다.

∵ 인덱스를 생성하는 것보다, SQL문을 처음부터 효과적으로 짜는 방향이 best

Index의 구조

참고 자료 : https://www.youtube.com/watch?v=iNvYsGKelYs

** Index는 RDB의 테이블과 논리적/물리적으로 독립적!

└ RDB 테이블은 정렬X, 입력순서대로 || Index는 key컬럼과 RowId컬럼 2개로 이뤄져 정렬 가능

** 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보단 작다

└ RDB처럼 테이블의 세부항목을 모두 갖지 않고 Key와 ROWID만 갖기 때문

ROWID : row(행-가로)를 식별하기 위해 갖는 물리적인 주소 정보

  • Search Key

    index에서 검색하기 위해 사용되는 column 또는 column의 집합

    한 테이블에서 다른 search key를 갖는 다수의 index가 생성 가능해짐

  • Files

    MySQL에서 테이블 생성시, 3가지 파일이 생성됨

    • FRM : 테이블 구조 저장 파일
    • MYD : 실제 데이터 파일
    • MYI : Index 정보 파일

      └ 쿼리를 이용하여 Index를 사용하는 column을 검색시, MYI 파일의 내용을 활용함

Index 작동 원리

🔗참고 url

  1. 이미 사용하고 있는 RDB에 INDEX를 걸어주는 방법
SELECT * FROM player WHERE name = 'Sonny';
SELECT * FROM player WHERE team_id = 105 and backnumber = 7;

/**(1) name에 index를 걸기**/
CREATE INDEX player_name_idx ON player(name); 
//name은 중복이 있을 수 있으므로 player테이블의 name attribute에 대해서 index를 만들기 

/**(2) team_id와 backnumber 에 index를 걸기**/
CREATE UNIQUE INDEX team_id_backnumber_idx ON player(team_id,backnumber);
//                                                   └ multicolumn index(composite index)

  1. 테이블을 생성하면서 처음부터 INDEX를 걸어주기
create table player (
 id         INT           PRIMARY KEY, //primary key에는 index가 자동으로 생성됨
 name       VARCHAR(20)   NOT NULL,
 team_id    INT
 backnumber INT
 INDEX player_name_idx(name),
 UNIQUE INDEX team_id_backnumber_idx(team_id,backnumber) 
 //                                   └ multicolumn index(composite index)
);

  1. 인덱스 정보들을 알고싶을 경우
SHOW INDEX FROM player;

multicolumn index는 seq_in_index가 순차적으로 증가됨 ⇒ column_name으로 attribute 확인하기

인덱스를 만들 때 고려해야할 사항

  • 인덱스가 언제 사용될 것인가 ?
    • 정확하게 key와 일치하는 row들을 찾을 때 사용할 것인가 ?
    • Range Query에 사용하나?
    • 테이블에 모든 row들을 조회할 때 사용할 것인가?
  • 테이블이 얼마나 자주 업데이트 되는가?
    • DML은 index 관리를 위한 update가 발생함
  • 인덱스의 key가 super key or primary key?
  • 하나의 key로 여려 row들이 가능한가 ? Unique or not

언제 Index를 사용해야할까?

  • 규모가 큰 테이블
  • INSERT, UPDATE, DELETE가 자주 발생하지 않는 칼럼
  • JOIN이나, WHERE 또는 ORDER BY에 자주 사용되는 칼럼
  • 데이터의 중복도가 낮은 칼럼 (=카디널리티가 높은 칼럼)

[정리VER]

  1. Cardinality(카디널리티)

    ✨ 높을수록 인덱스 설정에 좋은 칼럼

    (= 한 칼럼이 갖고 있는 값의 중복도가 낮을 수록)

    즉, 카디널리티 = 1/중복도

  1. Selectivity(선택도)

    ✨ 낮을 수록 인덱스 설정에 좋은 칼럼

    = 칼럼의 특정 값의 row 수 / 테이블의 총 row 수 * 100

  1. 활용도

    ✨ 활용도가 높을 수록 인덱스 설정에 좋은 칼럼

    = WHERE 절에 자주 활용되는지

  1. 중복도

    ✨ 중복도가 없을 수록 인덱스 설정에 좋은 칼럼

인덱스의 자료구조

Index 종류

분류Index 종류DEF
유일성Unique IndexIndex 키는 연관된 테이블의 하나의 행만 가리킴(중복이 없음)
Non-Unique IndexIndex 키는 연관된 테이블의 여러 행을 가리킴 (중복이 있음)
구성 컬럼 수Single Index하나의 column으로 구성된 Index
Composite Index여러개의 column으로 구성된 Index(32개까지)
클러스터Clustered Index데이터의 순서가 Index 페이지의 정렬순서와 동일 ⇒ 한 테이블에 중복을 허용하지 않음 ⇒ Order By를 사용하지 않아도, 데이터가 정렬되있으므로 가장 빠른 처리 ⇒ 기본적으로 PK INDEX는 Clustered Index
Non-Clustered Index데이터의 순서가 Index 페이지와 상관없이 저장
함수Function-Based Index함수 or 표현식의 계산값으로 인덱스 생성
기타Bitmap Index비트를 이용하여 칼럼값을 저장, rowID를 자동으로 생성
Reverse key IndexIndex칼럼의 순서는 유지, 해당 column값의 각 바이트 위치를 거꾸로 저장

Hash Table

참고 자료 : https://aeroej.tistory.com/151
  • 칼럼 값으로 생성된 해시를 기반으로 인덱스를 구현

    └ 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색하는 등 값의 일부만으로 검색하므로할 때는 해시 인덱스 사용 불가능 !! ⇒ 메모리 기반의 데이터베이스에서 많이 사용

Process

  • 검색하고자 하는 키 값을 입력받음
  • 해시 함수를 통해 HashCode 반환
  • 배열의 Index로 환산
  • Value에 접근

장점

  • 시간복잡도 : O(1) : 검색용이

문제점

  • 부등호(>,<)와 같은 연속적인 데이터를 위한 순차 검색은 X
  • 해시 충돌
    • 키 값은 무한대지만, HashCode는 정수개로 한정되기에 중복되는 HashCode를 갖는 충돌발생

B-Tree

**여기서 B : Balanced ⇒ 한쪽으로 쏠리지 않도록 트리가 재정렬됨

참고자료 : https://www.youtube.com/watch?v=iNvYsGKelYs

B+Tree

참고자료 : https://www.youtube.com/watch?v=iNvYsGKelYs
  • 자식 노드가 2개 이상 (B-Tree를 개선시킨 자료구조)
  • 데이터는 맨 밑의 노드들만 보관하고, 위에는 가이드만 제공한다
  • B-Tree의 리프노드들을 LinkedList로 연결하여 순차 검색을 용이하게 함 (⇒ 범위검색이 매우 쉬워짐)
  • 해시 테이블보단 O(logn log n)의 시간복잡도를 갖지만, 더 흔하게 사용됨

구분B-TreeB+Tree
데이터 저장리프노드, 브랜치 노드 모두 데이터 저장오직 리프 노드에만 데이터 저장
트리의 높이높음낮음 ⇒ 한 노드 당 key를 많이 담을 수 있음
풀 스캔시, 검색 속도모든 노드 탐색리프 노드에서 선형탐색
키 중복XO ⇒ 리프 노드에 모든 데이터가 있기에
검색- 자주 access되는 노드 : 루트노드 근처 └ 브랜치 노드에도 데이터가 존재하기에 빠름리프노드 까지 가야 데이터가 존재
LinkedListx리프 노드끼리 LinkedList로 연결

💡
왜 해시테이블이 아닌 B+Tree를 사용할까?
  • 해시테이블은 동등연산(=)에 특화되어 있어서 데이터베이스의 자료구조에 적합하지 않다.
  • 해시테이블에 저장되는 값들을 정렬되어 있지 않기에 특정 값보다 크거나, 작은 값(>,<)을 찾을 수 없다.

    ∵ SQL 쿼리문에서 특정 범위의 값을 조회하는 경우, 특정 값보다 크거나, 작은 값을 찾을 수 없다.

  • 반대로 B+Tree는 SELECT를 할 때, =, >, <처럼 모든 범위탐색도 가능
  • 노드마다 배열로 구현되어 있기 때문에 방대한 데이터 접근이 가능하다 .
💡
그러면 HashTable은 db에서 어떨 때 사용이 될까?

Index로는 부적합하지만, Join하는 경우(’=연산자’ 사용)에 사용된다.

적은 데이터의 테이블을 메모리에 HashTable로 올려두고, HashJoin을 사용할 때 빠르게 조회할 수 o


Uploaded by N2T

'CS > 데이터베이스' 카테고리의 다른 글

DBMS & RDBMS  (0) 2023.08.23

'CS/데이터베이스'의 다른글

  • 현재글인덱스란 ?

관련글

티스토리툴바