DB Index 란

jodong2 2022. 8. 15. 18:32

2022. 8. 15. 18:32

Index란?

Index(색인) : 책 속의 낱말이나 구절, 또 이에 관련한 지시자를 찾아보기 쉽도록 나열한 목록

이 단어는 어디있구나, 이 내용은 어디있구나 를 알려주는 페이지로
책이 100페이지가 있다면 위의 이미지와 같은 페이지가 1~2페이지는 존재할것이다.

대충 책의 1%가 인덱스 페이지라고 가정하자.

책 전체를 안훑어보고 1%만 훑어봐도 원하는 내용의 위치를 찾을 수 있다. 대충 찾는 속도가 100배 빨라졌다.

그럼 만약 책이 1000000011장으로 구성되어있다면 10000000장은 인덱스 페이지로 쓰일 것이다. 10000000장 중에 내가 원하는 내용의 위치가 적힌 페이지를 찾는건 100배 빨라졌다하더라도 답답할 따름이다.

따라서 인덱스 페이지 내에서도 원하는 내용이 적힌 페이지가 명시된 부분을 찾기 쉽게 할 필요가 있다. 위의 이미지를 다시 한 번 보자. 단어들은 알파벳순으로 정렬되어 있다. 내가 찾는 단어가 Bae정현이라면 B로 시작하는 부분만 찾으면 된다. 알파벳 별로 분포가 균일하다면 대충 100배에서 추가로 26배 빨라졌다. 2번째 알파벳도, 3번째 알파벳도 순서대로 정리 되어있겠지만 처음 알파벳까지만 봐도 2600배 빨라졌다.

책의 페이지 중 1%를 희생해서 원하는 정보를 빠르게 찾을 수 있도록 도와주는 것이 인덱스의 역할이다.

DB에서의 Index

Q1-1) DB작업을 할 때 속도가 느린 상황입니다. 무엇을 고려할껀가요?
A1-1) DB 작업을 할 때 속도저하가 발생하는 대부분의 작업은 SELECT문, 조건 검색 WHERE절에서 발생합니다. 먼저 SQL문이 효율적으로 작성되어 있는지 확인한 뒤 문제가 없다면 Index를 고려해볼 수 있습니다.

Q1-2) Index가 뭔가요 ?
A1-2) 인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료 구조입니다.

Q1-3) Index는 어떻게 속도를 높여주나요 ?
A1-3) 별도의 저장공간을 할당하여 데이터의 위치정보를 Value값, 찾고자 하는 정보(Column)를 Key 값인 Key - Value 형태로 저장하고 Key값을 기준으로 정렬하여 (== B Tree를 만들어) 탐색을 빠르게 해줍니다.

Q1-4) 그럼 모든 컬럼에 Index 테이블을 만들어주면 데이터베이스는 속도가 빨라지나요??
A1-4) 아닙니다. 인덱스 테이블은 항상 정렬된 상태를 유지해야 하기 때문에 읽기작업이 아닌 쓰기, 수정작업이 많이 필요한 테이블에 인덱스가 존재할 경우 성능이 저하됩니다.

데이터베이스의 인덱스도 책의 인덱스와 같은 메커니즘이다.

원하는 데이터의 위치를 빠르게 찾아 읽을 수 있도록 별도의 저장공간을 할당하여 데이터(Key)의 위치정보(Value)를 저장한다.그리고 별도의 저장공간 속에서도 원하는 정보를 찾기 쉽게 인덱스 데이터를 정렬(B Tree)한다.

즉 인덱스에서 내가 원하는 데이터(키워드)를 먼저 찾고, 같이 저장되어있는 물리적 주소로 찾아가서 그 키워드에 대한 정보를 읽을 수 있다.

인덱스의 활용

1) 조건 검색 Where 절의 효율성

테이블을 만들고 안에 데이터가 쌓이게 되면 데이터(record ,row)들은 내부적으로 순서가 없이 뒤죽박죽 저장된다.

예를들어 아래의 테이블에서 레코드는 순서 없이 저장된다. (물리주소는 아래 인덱스테이블의 이해를 돕기 위해 표시했다.)

ID	이름	나이	혈액형	주언어	멋	물리주소
wh1	조현동	27	B	Python	9999	10
dl1	이안채	27	O	Java	32	01
wh2	조현동	27	B	한국어	9999	00
qo1	배정현	27	AB	C++	31	11

만약 여기서 이름이 조현동인 데이터를 찾고 싶다면 다음과 같은 쿼리가 필요하다.

SELECT 이름
FROM 스터디A
WHERE 이름="조현동"

이때 데이터베이스는 WHERE절의 조건에 맞는 데이터들을 모두 찾기 위해 테이블내의 데이터를 처음부터 끝까지 읽고 조건과 맞는지 비교하는 작업을 수행한다. (== Full Table Scan)

하지만 인덱스 테이블은 데이터들이 설정된 컬럼 값이 정렬되어 저장된다. 따라서 해당 조건에 맞는 데이터들을 보다 빠르게 찾아낼 수 있다.

예를들어 다음과 같은 인덱스 테이블이 존재한다. (여기서는 위의 예시 테이블과 다르게 실제로 물리주소가 저장된다.)

이름	물리주소
배정현	11
이안채	01
조현동	00
조현동	10

인덱스테이블은 이름순(ㄱㄴㄷ)으로 정렬되어있고 조현동을 찾기 위해 이진탐색이든 뭐든 사용하여 기존의 WHERE 절에서 많은 시간을 차지하던 풀 테이블 스캔방식보다 빠르게 원하는 정보의 물리주소를 찾을 수 있을것이다.

2) 정렬 ORDER BY 절의 효율성

인덱스를 사용하면 이미 정렬되어 있으므로 ORDER BY에 의한 정렬 과정을 생략할 수 있다.

ORDER BY또한 부하가 큰 작업중 하나이다. 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생된다. 인덱스를 사용하면 이러한 전반적인 자원의 소모를 하지 않고 이미 정렬된 인덱스 테이블을 가져다 보여주면 되므로 ORDER BY 절 또한 빠르고, 간단하게 처리할 수 있다.

3) MIN, MAX의 효율적인 처리

정렬되어 있지 않은 데이터에서 MIN값과 MAX값을 찾으려면 FULL TABLE SCAN으로 찾아야한다. 이미 정렬되어 있는 INDEX TABLE을 활용하면 처음 값(혹은 마지막 값)을 가져오면 된다.

그럼 모든 데이터에 대해 인덱스를 만들어주면 빠르게 찾고 좋지 않을까?

책의 예시를 보자. 극단적으로 생각해보면 책 한권의 내용을 한 번 더 뒤에 정렬해서 붙여야한다. ~~그럼 100페이지 책도 200페이지 가깝게 되고 대한민국 학생들은 승모근때매 얼굴이 커보이는 상황이 발생한다.~~

이러한 극단적이고 1차원적인 상황을 포함해서 왜 인덱스를 남발하면 왜 안될까??

인덱스를 남발하면 안되는 이유

가장 큰 이유는 정렬이다. 인덱스는 정렬때매 사용하고, 정렬때매 남발하면 안된다.

인덱스 테이블은 항상 정렬된 상태를 유지해야한다. 정렬된 테이블에 새로운 인덱스 데이터를 넣어보자. 2022년 8월 14일까지 알려진 자료구조에는 원하는 순서(위치)에 데이터를 삽입하는 경우 최소 O(logN)의 시간복잡도가 필요하다. 삽입할때만 문제가 아니다. 테이블에서 값이 변경되면, 그에 해당하는 인덱스 테이블의 값도 변경해야하고, 변경된 값을 기준으로 다시 위치를 찾아 인덱스 테이블을 정렬해야한다.

1) DML에 취약하다.

일반 테이블에서 INSERT, UPDATE, DELETE 문이 수행되면 인덱스 테이블은 바빠진다.

예를 들어 일반 테이블에서 값을 UPDATE했다. 그럼 인덱스테이블에서 변경된 값을 찾아야하고 수정해서, 정렬해야한다.

데이터를 저장하기 위해 흔히 *트리구조(B, B+ 트리구조)를 사용한다. 트리구조의 특성상 값이 변경 될 경우 해당위치의 노드를 삭제하고 정렬 후 새로운 값을 넣어 재정렬을 해야한다. 이런 과정을 UPDATE, DELETE문을 만날때마다 실행하면 성능(속도)이 안좋아 질 수 밖에 없다.

이러한 문제를 조금이나마 해소하고자 인덱스는 DML문을 만나면 아래와 같이 작업을 수행한다.

- INSERT : 새로운 데이터에 대한 인덱스 추가.

- UPDATE : 변경하는 인덱스를 사용하지 않음 처리(변경 후 자식 노드들에 대한 추가 정렬과정이 필요 없어짐) 이후 변경된(새로운) 데이터에대해 인덱스 추가 후 정렬.

- DELETE : 삭제하는 인덱스를 사용하지 않음 처리(삭제 후 정렬과정 필요 없어짐)

이런짓을 해도 여전히 일반 테이블보다 많은 작업을 필요로한다.

또한 사용하지 않음 처리는 실제로 삭제되는것이 아니기 때문에 인덱스테이블이 과도하게 커지는 문제가 발생할 수 있다.

따라서 DML이 빈번한 테이블보다는 검색을 위주로 하는 테이블에 INDEX 생성하기를 추천한다.

2) 인덱스 스캔이 무조건 더 빠르고 좋은것은 아니다.

인덱스로 값을 가져오는게 개사기인거처럼 말해놨지만 사실 항상 FullTableScan보다 좋은건 아니다.

대량의 데이터(넓은 범위의 데이터)를 읽어야 할 경우, 데이터의 형식이 적은경우 인덱스 스캔을 다시 한 번 생각해봐야한다.

~~(아래는 이해가 안되가지고 여러블로그 참조해서 억지로 이해한 내 판단이고 반박시 반박이 맞을 확률 큼)~~

넓은 범위의 데이터 액세스작업이 필요하다면 Full Table Scan이 효율적이다. 인덱스 스캔의 경우 값을 한 번에 읽어들이는 양(버퍼)이 적지만 Full Table Scan은 한 번에 읽어들이는 양이 많다. 따라서 인덱스 스캔은 빠르게 찾더라도 I/O작업이 여러번 발생하는 반면 FullTableScan은 느리게 찾지만 I/O작업이 적게 발생한다. ( 두개의 시간차이를 고려해서 DBMS는 넓은 범위를 읽고자 할 때 INDEX가 존재하더라도 Full Table Scan 한다. )

넓은 범위라 했지만 사실 그렇게 넓은 범위도 아니다. 데이터의 양이 충분히 많을때 전체 데이터의 10~15% 이상의 데이터를 처리해야한다면, Full Table Scan이 효율적이다.

3) 속도 향상을 위해 인덱스를 많이 만드는것은 좋지 않다.

인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다. 무턱대고 인덱스를 많이 만들면 안되고, 장단점을 비교하여 장점으로 작용할수 있는 작업(좁은 범위 읽기)을 더 많이 할 경우, 인덱스를 사용하고 단점으로 작용할 수 있는 작업을 많이 할 경우 (넓은 범위 읽기, 수정, 삭제, 삽입) 인덱스를 포기하는 것이 적절하다.

어떤 컬럼을 인덱스로 만들어야 할까??

1. 조건절에 자주 등장하는 컬럼

2. 항상 = 으로 비교되는 컬럼

3. 중복되는 데이터가 최소한인 컬럼

4. ORDER BY 절로 자주 사용되는 컬럼

5. JOIN조건으로 자주 사용되는 컬럼

위의 조건들을 살펴보면 PK가 최선이자 주로 선택되는 인덱스이다.

만약 중복이 가능한 컬럼으로 인덱스를 생성하여 모든 데이터가 중복이라면, 일반 테이블과 검색속도가 같은 용량만 차지하는 ~~똥덩이~~ 악효과를 보여줄 것이다.

인덱스 자료구조

Q2-1 ) DB (INDEX)에서 사용하는 대표적인 자료구조가 무엇이 있을까요?
A2-1) 이진트리에서 발전된 B (B+)Tree가 주로 사용됩니다.
실제 데이터베이스는 B+트리가 주로 사용된다.

Q2-2 ) B트리가 뭔가요??
A2-2) 이진트리 중 leaf노드의 레벨차이가 최대 1인 균형이진트리, 균형이진탐색트리와 유사합니다. 균형이진탐색트리와는 다르게 하나의 노드에 여러개의 값을 가질 수 있으며, 여러개의 자식노드를 가질 수 있는 자료구조 입니다. 이때 자식노드로 가질 수 있는 최대 개수가 M이라면 M차 B Tree라고 불립니다.

Q2-3) B, B+트리의 차이점은 뭔가요??
A2-3)
B Tree는 모든 노드에 데이터를 저장하는 반면,
B+ Tree는 B트리에서 발전된 형태로 leaf노드(==Data 노드)에만 데이터를 저장하고, leaf노드가 아닌 노드(==Index, Inner 노드)에는 자식노드를 가리키는 포인터값만 가지고 있으며, leaf노드끼리는 linked list 구조로 연결되어있습니다.

Q2-4) 설명해주신 B+트리의 구조는 B 트리와 비교해서 어떤 이점을 갖게 되나요?
A2-4) B+ Tree는 전체 데이터를 순회할때 leaf 노드에 접근하여 linked list구조로 연결되어 있는 다른 leaf노드에 접근하면 되므로 전체 노드를 순회해야하는 B Tree보다 효율적으로 데이터를 순회할 수 있습니다.
A2-4++) B+ Tree에서 leaf노드가 아닌 노드(= 비단말 노드=Index, Inner 노드)는 데이터가 없어서 B Tree보다 Inner노드에 대해 차지하는 용량이 적으므로, 하나의 디스크 블록에 더 많은 Inner노드를 담을 수 있습니다. 이러한 이점은 Key를 탐색하기 위해 비교적 적은 디스크 블록만을 읽어도 됩니다. 따라서 디스크의 접근수를 줄임으로 속도를 높여줄 수 있고 디스크의 저장공간을 보다 효율적으로 사용할 수 있습니다.

+a)
https://www.cs.usfca.edu/~galles/visualization/BTree.html