인덱스
인덱스(Index)는 데이터베이스의 테이블에 대한 검색 속도를 향상 시켜주는 자료구조인다.
테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.
우리가 책을 볼때 인덱스라 하면 목차 혹은 색인을 의미한다. 책에서는 원하는 내용을 찾을 때 목차나 색인을 이용하면 훨씬 빠르게 찾을수 있지 않은가? 마찬가지로 테이블에서 원하는 데이터를 찾기 위해 인덱스를 이용하면 빠르게 찾을 수 있다.
빠르게? 그럼 좋은거잖아?
항상 그렇지만은 않다. 우리가 목차를 이용해서 원하는 페이지를 찾는건 무척이나 쉬운일 이지만 이 목차를 이용해서 페이지를 찾는 행위를 면밀하게 분석해보면 여러단계의 수행동작이 필요하다. 1.목차를 인지하고, 2.찾고자 하는 범위를 인지하고, 3.페이지를 넘겨가며 찾는다. 사람에겐 생각할 필요도 없이 쉬운 방법이지만 컴퓨터에게 이를 학습시키기엔 많은 단계가 필요할 것이다. 단계적으로 본다면, 1.원하는 페이지가 나올때 까지 넘긴다. 라는 행동이 더욱 단순간편해보인다.
결국은 컴퓨터가 수행하는 작업이기 때문에 작업의 효율이 중요하다. 서론이 길어졌다. 인덱스의 장단점을 바로 살펴보자.
Index의 장점
인덱스의 장점으로는 앞서 말했듯 데이터베이스의 테이블을 검색하는 속도를 향상시켜준다. 또 그에 따라 시스템의 전반적인 부하를 줄일 수 있다. 예를들어 10개의 데이터가 있다면 원하는 데이터를 찾을때 최대 10번의 탐색을 진행하면 된다. 운 좋으면 한 번에 찾을 수 있지만, 운이 나쁘면 10번을 탐색해야 한다. 그러나 1억개의 데이터 중에서 탐색을 해야 한다면..? 단순간편한 방법으로는 매우 힘들어보인다.
아니 그러니까 왜 좋은건대..?
테이블의 검색 속도를 향상 시켜준다는건 앞서 말한 예시처럼 대규모의 데이터를 검색해야 하는 경우에 큰 이점을 가질수 있다. 그리고 인덱스는 검색 속도를 향상 시켜주는 자료구조 이다.인덱스를 구현할 수 있는 자료구조를 살펴보면 그 이유를 알 수 있다.
인덱스를 구현할 수 있는 자료구조는 여러가지가 있는데 대표적으로는 해시 테이블(Hash Table)과 B-Tree, B+Tree가 있다.
1. 해시 테이블(Hash Table)
해시 테이블은 key와 value를 한 쌍으로 데이터를 저장하는 자료구조이다. (key,value)로 쌍을 표현하며, key 값을 이용해 대응되는 value값을 구하는 방식이다. 해시 충돌이라는 변수가 존재하지만 평균적으로 O(1)의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조이다.
해시테이블의 자세한 설명 (그림있음) 해시테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. Linked List 같은 경우 key를 순회하면서 값을 찾아내지만 배열은 대부분의 언어의 경우 내부적으로 메모리의 특정 주소에 직접 접근하는 형태이기 때문에 index만 알면 바로 접근이 가능하다.
예를들어 우리가 (Key,Value)가 ("Jonh Smith","123-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 먼저 index = hash_function("Jonh Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = "123-1234"로 전화번호를 저장하게 된다. 이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회 할 수 있다. 해시테이블의 평균 시간 복잡도는 O(1)이다.
("Jonh Smith","123-1234")
key("Jonh Smith") -> 해시함수 -> index값 계산 == 메모리주소
조회할때 array[index] = "123-1234"
*버킷 :: 실제 값이 저장되는 장소
[Hash 함수(해시 함수)]
해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 해시 테이블에 사용되는 대표적인 해시 함수로는 아래의 3가지가 있다.
1. Division method: 나눗셈을 이용하는 방법으로 입력값을 테이블 크기로 나누어 계산한다.(주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Foldinng : 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터 테이블 내의 주소로 사용하는 방법이다.
3.Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k) = (kAmod1)xm
4.Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.
해시값이 충돌하는 경우
그런데 만약 "john Smith"를 해시 함수를 돌려 나온 값과 "Post Malon"을 해시 함수로 돌려서 나온 값으 동일하다면 이는 같은 메모리 주소에 2개의 데이터가 저장이 된다는 의미. 이는 있어서는 안될일이며 '충돌났다' 라고 표현하는데 해시테이블에서는 충돌에 의한 문제를 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.
좀더 자세한 내용은 -> 참고 :: https://mangkyu.tistory.com/102
해시 테이블을 이용한다면 인덱스는 (key,Value) = (컬럽의 값, 데이터 위치)로 구현하는데, 해시 테이블은 실제로 인덱스에서 잘 사용되지 않는다.
그 이유는, 해시 테이블은 등호(=) 연산에 최적화가 되어있기 때문이다. 데이터베이스에서 부등호(<,>)연산이 자주 사용되는데, 해시 테이블 내의 데이터들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간내에 찾을 수가 없다.
2.B-Tree
B-tree는 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 Balannced Tree의 일종이다. 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
B-Tree의 자세한 설명 (그림있음)
B-Tree가 되기 위한 조건은 다음과 같다.
- node의 key의 수가 k개라면, 자식 node의 수는 k+1개 이다.
- node의 key는 반드시 정렬된 상태여야 한다.
- 자식 node들의 key는 반드시 정렬된 상태여야 한다.
- root node는 항상 2개 이상의 자식 node를 갖는다. (root node)
- M차 트리일 때, root node와 leaf node를 제외한 모든 node는 최소 [M/2], 최대 M개의 서브 트리를 갖는다.
- 모든 leaf node들은 같은 leaf에 있어야 한다.
*leaf node :: 맨 아래 라인에 있는 노드들
이의 트리는 3차 B-Tree의 예시이다. 주황색 부분은 '자식 node 를 가리키는 포인터'이고, 살구색 부분은 '각 node의 key'이다. key와 데이터가 1대1 대응을 하고 있다.
node 안에서 key들은 항상 정렬된 상태를 유지하며, 이진 탐색 트리처럼 항상 각 key의 왼쪽 자식은 자신보다 작고, 오른쪽 자식은 자신보다 크다.
Balanced tree를 사용하는 이유는 뭘까? 일반적인 트리인 경우 탐색하는데 평균적인 시간 복잡도 O(logN)를 갖지만, 트리가 편향된 경우 최악의 시간 복잡도 O(N)을 갖게된다.
root node부터 탐색을 한다고 가정하고, 왼쪽처럼 편향된 트리에서 leaf node까지 탐색한다면 모든 node를 방문하기 때문에 O(N)의 시간이 걸리게 된다. 이러한 단점을 보완하기 위해 트리가 편향되지 않도록 항상 밸런스를 유지하는 트리가 필요하다. 자식들의 밸런스를 잘 유지하려면 최악의 경우에도 O(logN)의 시간이 보장이 된다.
B-Tree :: https://rebro.kr/169
B-Tree의 검색
B-Tree는 원하는 값을 어떻게 찾아줄까?
만약 우리가 찾는 값을 K라고 가정했을때
- root node부터 탐색을 시작한다.
- node의 key를 순회하여 K가 존재하면 탐색을 종료한다.
- K가 존재하지 않는다면 어떤 이웃한 두개의 key 사이에 K가 들어가는 경우 사이의 포인터를 통해 자식 node로 내려간다.
- leaf node까지 2~3을 반복한다.
14라는 key값을 찾아야 한다고 가정해보자.
실제 데이터베이스에서 한 node에 매우 많은 key가 포함될 수 있기 때문에, 정렬되어 있음을 이용하여 binary search등으로 효과적으로 찾을 수 있다.
B+Tree
기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.
B+Tree는 오직 leaf node, 맨 아래에 있는 노드에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다. 그리고 leaf node끼리는 Linked list로 연결 되어있다.
또, B+Tree에서 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.
그림으로 이해해보자
만약 14부터 20까지 모든 데이터를 찾아야 한다면 14를 찾은 과정을 찾으려는 찾으려는 데이터 수 만큼 반복해야 한다.
그렇기때문에 찾으려는 노드의 가작 작은 수 14부터 찾은 후 leaf node를 순회하면서 자료를 조회한다.
이러한 특성을 지니고 있어서 B+tree는 다음과 같은 장점을 지닌다.
1. leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리 자원을 더 확보 할 수 있다는것, 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.
2. Full scan을 하는 경우 B+tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked-list로 연결되어 있기 때문에 선형 시간이 소모된다.
단점
인덱스가 항상 정렬된 상태로 유지되어 오는 장점도 있지만, 그에 따른 여러 단점도 존재한다.
- 인덱스를 관리하기 위한 추가 작업이 필요
- 추가 저장 공간 필요
- 잘못 사용하는 경우 오히려 검색 성능 저하
인덱스를 항상 정렬된 상태로 유지해야 하기 때문에 인덱스가 적용된 컬럼에 삽입(insert), 삭제(delete) 수정(update) 작업을 수행하면 다음과 같은 추가 작업이 필요하다.
- INSERT : 새로운 데이터에 대한 인덱스를 추가
- DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행
- UPDATE : 기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가
이처럼 인덱스의 수정도 추가적으로 필요하기 때문에 데이터의 수정이 잦은 경우 성능이 낮아진다. 또, 데이터의 인덱스를 제거하는 것이 아니라 '사용하지 않음'으로 처리하고 남겨두기 때문에 수정 작업이 많은 경우ㅜ 실제 데이터에 비해 인덱스가 과도하게 커지는 문제점이 발생할 수 있다. 별도의 메모리 공간에 저장되기 때문에 추가 저장 공간이 많이 필요하게 된다.
또한 인덱스는 전체 데이터의 10% ~ 15% 이상의 데이터를 처리하거나. 데이터의 형식에 따라 오히려 성능이 낮아질 수 있디. 예를 들어 나이나 성별과 같이 값의 range가 적은 컬럼일 경우, 인덱스를 읽고 나서 다시 많은 데이터를 조회해야 하기 때문에 비효율적이다.
참고
인덱스의 개념 및 장단점 ::https://rebro.kr/167
