DB - 인덱스(Index) (B+Tree Index)

인덱스(index)란 무엇인가?

DataBase에서는 인덱스(index)를 굉장히 많이 사용한다. 인덱스(index)란 무엇인가? 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시켜주는 자료구조이다.

우리가 수천페이지가 넘는 책에서 필요한 내용을 찾는다고 했을때, 페이지를 차례대로 넘기면서 찾는다면, 처음부터 찾아봐야할 것이고 시간이 많이 소비되어 비효율적으로 내용을 찾을 것이다. 이때, 책에 필요한 내용이 인덱스(차례)에 명시되어있다면, 우리는 그 차례를 보고 해당위치의 페이지로 가서 빠르게 찾을 수 있을 것이다. 데이터베이스의 인덱스는 이러한 원리와 동일하다.

 

인덱스의 장점과 단점

- 장점

1] 테이블의 데이터를 조회하는 속도가 빨라져서 성능이 향상된다.

2] 전반적인 시스템 부하를 줄일 수 있다.

 

- 단점

1] 데이터 저장공간 이외에 추가로 인덱스정보를 저장할 공간이 필요하다.

2] 인덱스를 잘못사용할 경우 오히려 성능저하를 초래할 수 있다.

=> 데이터의 추가,변경,삭제가 많이 일어나는 테이블에 대해서는 성능이 좋지않을 수 있다. 변경이 일어날 때마다, 인덱스 데이터도 갱신이 이루어지기 때문이다.

 

인덱스를 사용하면 좋은 경우

1] 대규모의 데이터를 가지고 있는 테이블

2] 데이터의 추가,변경,삭제가 자주 일어나지 않는 테이블

3] JOIN이나 WHERE 또는 ORDER BY 정렬에 자주 사용되는 컬럼

4] 카디널리티(Cardinality)가 높은(중복이 많이없는) 컬럼

 

인덱스의 자료구조

= 해시 테이블(Hash Table)

: Key, Value 데이터로 저장하는 자료구조이며 빠른 데이터 검색이 가능한 자료구조이다. 0(1) (1번의 연산을 수행) 시간복잡도를 가지기 때문이다. 하지만 해시는 값이 조금이라도 달라지면 완전히 다른 해시값이 생성되기 때문에, 구조상 등호(=) 연산에만 최적화가 가능하며, 부등호(>, <) 연산에는 적합하지 않다.

= Binary Search Tree

: 트리형 자료구조이다. Binary Search Tree 자료구조는 각각 루트(Root)노드, 중간(Branch)노드, 리프(Leaf)노드로 구성되어있다.  원하는 데이터를 노드를 타고 내려가서 찾는다. 리프노드를 제외한 나머지 노드들을 2개(이진)의 자식노드를 가진다. 0(log n) (최대 n번의 연산을 수행)의 시간 복잡도를 가진다.

 

위의 그림을 보면, bear라는 데이터를 찾을때 2번의 연산으로 찾는다. 이런 구조를 가진 Binary Search Tree 자료구조는 데이터가 많아져도 복잡도가 크게 증가하지 않는다는 장점이 있다.

그러나, 데이터가 등록,수정,삭제가 일어남에 따라 한쪽 Branch로만 데이터가 몰릴 수 있다는 단점이 생겨난다. 시간이 지날수록 최악의 상황에서는 복잡도가 개선이 어려워지는 문제점이 생길 수 있다. 이런 문제점을 해소한 자료구조가 바로 아래에서 설명 할 B-Tree 이다.

 

= B-Tree (Balanced Tree)

이진 트리(자식 노드가 2개)와 비슷해보이지만, 이를 확장하여 하나의 노드가 2개보다 많은 N개를 가질 수 있는 구조이다.  B-Tree에서의 B는 Balance(=균형)의 의미로써 데이터가 변경되어 트리 균형이 흐트러지더라도 다시 균형을 회복하는 기능이 있다. 따라서 0(n) (n번의 연산을 수행)의 시간 복잡도를 가진다. 이 자료구조는 Key를 이용하여 찾고자하는 데이터를 트리 구조를 이용하여 찾는다. 

 

= B+Tree

기존의 B-Tree를 개선하여 나온 개념이다. 기존의 B-Tree의 특징을 따라가되, 몇가지 개선된 차이점이 존재하며, 가장 큰 차이점은 기존 B-Tree에서는 노드에 담기는 내용을 Key와 Data(=Value)를 모두 담아서 사용한다. 하지만 B+Tree는 리프노드를 제외한 나머지 노드에는 Data(=Value)를 저장하지 않는 특징이 있고, 리프노드끼리 LinkedList로 연결되어 있다.

B+Tree의 장점

1] 리프노드에만 Data를 저장하기 때문에 메모리를 더 확보할 수 있으므로 더 많은 Key들을 수용할 수 있다.

2] 모든 노드를 확인해야하는 B-Tree보다, 한번의 선형 탐색만 하면 되기때문에 더 빠르다.

 

B-tree vs B+tree

구분	B-tree	B+tree
데이터 저장	리프 노드, 브랜치 노드 모두 데이터 저장 가능	오직 리프 노드에만 데이터 저장 가능
트리의 높이	높음	낮음(한 노드 당 key를 많이 담을 수 있음)
풀 스캔 시, 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색
키 중복	없음	있음(리프 노드에 모든 데이터가 있기 때문)
검색	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름	리프 노드까지 가야 데이터 존재
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결

 

참고자료

= https://mangkyu.tistory.com/96

= https://beelee.tistory.com/37

= https://zorba91.tistory.com/293