Database_Index(인덱스)란?

Index란?

인덱스란 단어 그대로 책의 색인의 역할을 한다. 즉 데이터 베이스의 인덱스란, 데이터베이스 내에 저장된 데이터들의 목차가 기록되어 있다고 볼 수 있다. 데이터는 책의 내용이고, 데이터가 저장된 레코드의 주소는 인덱스 목록에 있는 페이지 번호가 될 것이다. 데이터 베이스에서 인덱스 없이도 데이터를 검색해서 가지고 오는 것이 가능하지만, 오래 걸릴 것이다. 이는 우리가 책을 읽을 때 목차 없이 원하는 곳으로 이동하려 할때 시간이 오래 걸리는 것을 생각하면 된다. 따라서, 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어 두게 된다.

 

인덱스 기능은 "내가 원하는 부분에 쉽고 빠르게 찾아서 전달해주는 역할"을 한다. 즉 "정보검색"과 관련된 성능을 최적화시켜줄 수 있는 유용한 도구이다.

 

DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는데는 빠르지만 새로운 값을 추가하거나 삭제, 수정하는 경우에는 실행 속도가 느려진다. 따라서 인덱스의 경우, 데이터의 저장 및 수정과 관련된 성능을 희생하고, 읽기 속도를 높이는 기능이 있다. 따라서 데이터베이스의 인덱스도 경우에 따라서 잘 선택해서 사용해야 한다.

 

사용해야 하는 이유

만약에 인덱스를 사용하지 않고, 값을 SELECT 하는 경우라면, 데이터베이스 내부적으로, 해당 테이블을 다 조회하면서, 값에 해당하는 데이터를 반환하게 될 것이다. 만약에 데이터 조회가 자주 일어나는 서비스에 엄청 많은 데이터가 저장되어 있다면, 원하는 값을 반환하기 위해서 수많은 데이터를 다 조회해야할 것이고, 트래픽에 따라 성능이 저하될 수 밖에 없을 것이다. 따라서 자주 조회되는 칼럼에 대해서는 인덱스 테이블을 따로 만들어서 SELECT 문이 들어왔을 때, 인덱스 테이블에 있는 값들로 결과 값을 조회해 온다. 

 

왜 일반적으로 인덱스를 생성할 때 b-tree 알고리즘을 사용할까?

데이터에 접근하는 시간복잡도가 O(1)인 hash table이 더 효율적일 것 같지만, hash table을 사용하게 된다면, 등호연산이 아닌 부등호 연산의 경우에 문제가 발생한다. hash table은 동등연산에 특화된 알고리즘이다.

1. 인덱스를 생성하게 된다면, 생성, 삭제 수정 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생한다.
   생성의 경우, 인덱스에 대한 데이터도 추가해야 하므로 그만큼 성능에 손실이 따른다.
   삭제의 경우 인덱스에 존재하는 값은 삭제하지 않고, 사용안한다는 표시로 남게된다. 즉 row의 수는 그대로인 것이다.
   이 작업이 반복되면 어떻게 될까?실제 데이터는 10만건인데 데이터가 100만건 있는 결과를 낳을 수도 있는 것이다.
   수정의 경우는 생성과 삭제가 동시에 일어나는 만큼 두 경우의 단점을 다 수반하게된다.
2. 칼럼을 이루고 있는 데이터의 형식에 따라서 인덱스의 성능이 악영향을 미칠 수 있다.
   대표적으로 값의 range가 적은 데이터 즉, 성별에 대해서는 인덱스를 생성하면 비효율 적이다.
   이런 경우에는 인덱스를 읽고 다시 한 번 디스크 I/O가 발생하기 때문에 비효율적이다.

 

그렇다면 위에서 언급된 해시색인, B-Tree 색인과 더불어 LSM-Tree 등 데이터 베이스 내에 색인을 생성하는 주요 알고리즘에 대해서도 간단하게 정리해 보려 한다. 

LSM-Tree에 대해서는 아직 100%이해했다고 보기가 어려워서 계속 추가적으로 공부하고 보완할 예정이다.

 

Index 동작 방식

• A 테이블 생성 시 B칼럼에 대한 인덱스를 주면 B칼럼에 대한 인덱스 테이블이 생성
• A 테이블에 B 칼럼에 대한 WHERE문이 포함된 쿼리가 나갈 때, 해당하는 값을 인덱스 테이블에서 찾는다.
• 해당 값의 table_id[PK] 값을 가져온다,
• 이 table_id 값으로 A 테이블에서 값을 조회한다.

 

Index 알고리즘

 

B+- Tree 인덱스 알고리즘

일반적으로 사용되는 알고리즘이다. 해당 알고리즘은 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘이다. 

-> 실제로는 값의 앞부분만 잘라서 관리한다.

B+-Tree 구성

• 리프노드 : 실제 데이터가 저장되는 노드
• 논리노드 : 리프노드까지의 경로 역할을 하는 노드
• 루트노드 : 경로의 출발점 노드

리프노드에 이르기까지 자식노드에 대한 포인터가 저장되어 있어서 탐색에 있어 루트노드에서 어떤 리프노드에 이르는 한 개의 경로만 검색하면 되기 때문에 검색에 있어 매우 효율적인 알고리즘이다.

 

B-Tree는 binary search tree의 한계를 극복하고자 나온 자료구조이다.

DBMS에서 가장 범용적으로 사용되고 있는 자료구조이며, 파생으로 나온 B+Tree Index, B*-Tree Index 등이 있다.

 

Balanced Tree는 구조적으로는 Binary Search Tree와 비슷하지만, 데이터 높이(층)를 자동으로 바로잡아주는 기능이 있다.

이는 데이터의 Insert, delete등의 시간을 희생시키면서 Search 시간을 줄일 수 있다.

 

색인안에 바로 색인된 로우를 저장하여 성능의 최적화를 끌어내려 하는데 이를 클러스터드 색인이라고 한다.

대표적으로 mySQL의 innoDB 저장소 엔진에서는 기본키가 언제나 클러스터드 색인이고 보조 색인은 기본키를 참조한다.

 

루트로 시작해서 개별 키를 포함하는 페이지에 도달 -> 값을 포함하거나 값을 찾을 수 있는 페이지의 참조를 포함(row id).

트리가 계속 균형을 유지하는 것을 보장한다. 대부분의 데이터베이스는 B트리의 깊이가 3~4단계 정도면 충분하다.

 

신뢰성 : 다중 스레드가 동시에 B트리에 접근한다면 동시성 제어를 해야한다. 스레드가 일관성이 깨진 상태의 트리에 접근. 

보통 래치(latch)로 트리의 데이터 구조를 보호한다.

 

페이지에 전체 키를 저장하는 게 아니라 키를 축약해 쓰면 공간을 절약 -> 트리 깊이 수준을 낮출 수 있다.

 

LSM트리는 보통 쓰기에서 빠른 반면, B트리는 읽기에서 더 빠르다고 여긴다.

(왜 쓰기에는 적절하지 못할까? b tree가 균형을 맞추는 작업을 해줘야 하므로)

이와 관련해서는 아래에서 한 번더 언급될 예정이다.

즉 B-Tree 인덱스는 읽기 성능은 높이지만 쓰기 과정에 오버헤드가 생긴다.

 

Hash 인덱스 알고리즘

칼럽의 값으로 해시값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 해시 알고리즘에 대한 글은 블로깅해 두었으니 해당 링크를 참고하면 된다. 

해당 알고리즘은 값을 변형해서 인덱싱하므로, 특정문자로 시작하는 값으로 검색을 하는 등 값의 일부만으로 검색하고자 할때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터 베이스에서 많이 사용한다.

 

메모리에 저장해야 하므로 디스크가 가득 찼을때 확장하는 비용이 비싸고 해시 충돌 해소를 위해 성가신 로직이 필요하기 때문이다.

원칙적으로는 디스크에 해시 맵을 유지할 수 있지만 성능이 안 좋다.

 

이를 위한 해결책으로 특정 크기의 세그먼트로 데이터를 나누어 저장하는 컴팩션(일종의 압축)을 수행하는 것이다.

이렇게 컴팩션을 수행하는 작업은 백그라운드 스레드에서 수행하며, 그동안 이전 세그먼트 파일을 통해 읽기와 쓰기 요청 처리를 진행한다. 병합과정이 끝난 이후에는 읽기 요청은 이전 세그먼트 대신 새로 병합한 세그먼트를 사용하게끔 전환한다.

전환 후에는 세그먼트 파일을 간단히 삭제한다. 이를 컴팩션이라 한다.

 

SS테이블과 LSM트리(참고)

• SS테이블(Sorted string Table) : 키로 정렬된 형식. 각 키는 세그먼트 파일 내에 한 번만 나타나야 한다. 키값쌍으로 저장된 데이터를 키로 정렬된 형식의 문자열 테이블이다.
• LSM 트리(Log-Structured Merge-Tree) : 정렬된 파일 병합과, 컴팩션 원리를 기반으로 하는 저장소 엔진

루신에서 엘라스틱서치, 솔라에서 사용하는 전문 검색 색인 엔진.

병합시에 병합정렬 알고리즘에서 사용하는 방식과 유사해서 파일이 사용가능함.

메모리보다 파일의 용량이 더 크더라도 간단하고 효율적이다.

 

또한 특정 키를 찾기 위해서 모든 키의 색인을 유지할 필요 없다. 해당 테이블에는 키들이 이미 정렬되어 있기 때문에, 가령 10이라는 키를 찾기 위해서는 10보다 작으면서 가장 가깝고, 크면서 가장 가까운 두 키를 찾아서 그 사이에 있다고 가정하여 키를 찾으면 되기 때문이다.

대표적으로 Hbase와 카산드라 엔진

 

Linked List를 Sorted Array로 바꾸면 Read 성능을 향상시킬 수 있다.(링크)

- 이때부터 SS 테이블을 사용하게 된다.

 

클라이언트에서의 쿼리를 Log 형태로 메모리에 저장하다가, 메모리가 임계점에 다다르면 DB에 Sorted String Table로 Flush한다.

Log Structured Merge Tree(LSM트리)에서는 Update에 대해 Update-in-Place가 아닌 Append 방식으로 수행한다.

분산된 Record들에 대해 Position을 찾은 후 Update 하는 과정을 제거함으로서 Write 성능을 개선했다.

Data를 읽을 때는 최신 값들이 존재하는 MemTable을 먼저 탐색한다. 탐색에 실패했을 경우 Disk의 파일들을 최신 순으로 검사한다.

그러나 파일의 수에 비례하여 시간이 걸리는 문제가 있다.

이를 보완하기 위해 파일 인덱스나 파일의 블록 인덱스를 만들어 메모리에 캐싱해 놓는 방법도 있다.더 나아가 블룸 필터를 사용하여 탐색 시간을 줄여보려는 방법도 존재한다.하지만 이것은 Read 성능을 올려주는 대신 Write의 오버헤드를 증가시킨다. 그러나 상대적으로 매우 낮은 Read 성능을 끌어올리기 위해 Write 성능을 약간 희생하는 것은 나쁘지 않다.

 

블룸 필터를 사용하면?

해당 파일에 특정 rowkey에 해당하는 데이터가 있는지 즉시 알 수 있다.

• 모든 파일에 scan을 수행하지 않아도 된다!
• 블룸 필터가 파일이 있다고(positive) 판별해도, 실제 없을 수 있다(false) : false-positive
• 하지만, 파일이 없다고(negative) 판별하면, 실제로 있는 경우(false)는 발생하지 않늗다. : Never false-negative

 

Index 생성

 

CREATE (UNIQUE) INDEX 인덱스 명칭

ON 테이블명(컬럼명 1 ACS/DESC, 컬럼명....)

 

-> UNIQUE의 경우, 데이터 중복 사용여부에 따라서 선택해서 사용하면 된다.

 

 

Index 종류

인덱스는 기존 테이블과 달리, 데이터 중복성을 가질 수 있다. 

 

키에 따른 인덱스 분류

• 기본 인덱스(Primary index) : 기본키를 포함하는 인덱스(키의 순서가 레코드의 순서를 결정)
• 보조 인덱스(Secondary Index) : 기본 인덱스 이외의 인덱스(키의 순서가 레코드의 순서를 의미하지는 않음)

파일조직에 따른 인덱스 분류

• 집중 인덱스(Clustered Index) : 데이터 레코드의 물리적 순서가 그 파일에 대한 인덱스 엔트리 순서와 동일하게 유지되도록 구성된 인덱스. cluster란 여러개를 하나로 묶는다는 의미로 주로 사용된다. 집중 인덱스에서 clustered는 비슷한 것들을 묶어서 저장하는 형태로 구현되는데 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안된 것이다. 
  여기서 clustered index는 위에서 설명한 PK에 대해서만 적용되는 내용이다. 즉 PK가 비슷한 레코드끼리 묶어서 저장하는 것이다. 
• Composite index : 클러스터드 인덱스가 아닌 경우 중에서, 인덱스로 설정하는 필드의 속성을 기준으로 하는 인덱스이다. 

 

Index의 성능

그렇다면 Index를 사용하는 것이 항상 좋을까? 정답은 No이다. 그 이유에 대해서는 크게 두가지로 정리할 수 있다.

 

1) 인덱스를 생성하게 된다면, 생성, 삭제 수정 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생한다. 생성의 경우, 인덱스에 대한 데이터도 추가해야 하므로 그만큼 성능에 손실이 따른다. 삭제의 경우 인덱스에 존재하는 값은 삭제하지 않고, 사용안한다는 표시로 남게된다. 즉 row의 수는 그대로인 것이다. 이 작업이 반복되면 어떻게 될까?

실제 데이터는 10만건인데 데이터가 100만건 있는 결과를 낳을 수도 있는 것이다.  수정의 경우는 생성과 삭제가 동시에 일어나는 만큼 두 경우의 단점을 다 수반하게된다. 

 

2) 칼럼을 이루고 있는 데이터의 형식에 따라서 인덱스의 성능이 악영향을 미칠 수 있다. 대표적으로 값의 range가 적은 데이터 즉, 성별에 대해서는 인덱스를 생성하면 비효율 적이다. 이런 경우에는 인덱스를 읽고 다시 한 번 디스크 I/O가 발생하기 때문에 비효율적이다. 

 

 

 

Reference

 

참고자료 1

참고자료 2

참고자료 3