Index정리

Index란❓

데이터베이스 테이블의 검색 속도를 향상 시키기 위한 자료구조이다.

 

장점으로는 검색 속도를 향상 시킬 수 있다. 즉 조회 성능을 향상 시키기 위해서 사용하는 것이다.

 

그럼 어떤 단점이 있을까?

단점으로는 인덱스를 관리하기 위한 별도의 공간이 필요하다.(DB의 약 10%)

인덱스를 관리하기 위해, 인덱스 추가, update, delete 작업이 필요합니다. 그래서 잘못 사용하는 경우에는 오히려 성능을 저하시킬 수 있습니다.

 

Index는 어떤 자료구조를 사용할 까❓

먼저 정답부터 말하자면 B+tree(Mysql기준)를 사용한다.

 

그럼 왜 B+tree를 사용할까?

b+tree는 b-tree에서 나온 자료구조이다. 또 b-tree는 이진 검색 트리에서 나온 자료구조이다. 

 

이진 검색 트리의 특징을 먼저 살펴본다면, 이진 검색 트리는 한 노드가 두 개이하의 자식 노드를 가지고 있다.

왼쪽 자식은 자신보다 작은 값을 가진 노드, 오른쪽 자식은 자신보다 큰 값을 가지고 있는 노드로 이뤄진다.

그래서 어떤 데이터를 찾고 싶을 때 평균적으로 O(logN)의 값을 가진다. 즉, 트리의 높이 만큼만 탐색을 하면 원하는 값을 얻을 수 있다는 것이다. 하지만, 이것은 어디까지나 "평균적"일때다. 최악일 때, 트리가 한 쪽으로 쏠려있을 때는 O(N)의 시간복잡도를 가진다.

 

이진 탐색 트리의 이 문제점을 해결하기 위해서, balanced-tree가 나왔다. Balanced-Tree는 트리의 노드가 한 방향을 쏠리지 않도록, 밸런스를 맞추는 것이다. 그래서, 가장 작은 높이를 유지하도록, 만드는 것이다. Balanced-Tree에는 RedBlack-Tree, AVL 등 이 존재한다.

 

그러면 왜 여기서, 왜 RedBlack-Tree가 아닌, B-tree를 사용했을까? 

 

RedBlack tree는 한 노드의 "하나"의 값만 가질 수 있다. 그리고 좌,우 자식 노드의 개수 밸런스를 맞춘다. 노드의 하나의 데이터만 저장하고 있다면, 결국 값이 많아지면 tree의 높이가 높아진다. 하지만, B-tree는 한 노드에 "여러" 데이터가 저장될 수 있다. 그리고 노드는 배열로 이뤄져 있다. 한 노드의 자식들은 (N+1) 만큼 존재할 것이다. 그렇기 때문에, RedBlack-tree와 같은 양의 데이터를 가지고 있다 하더라도, B-tree의 높이가 더 낮을 것이다. 그래서, RedBlack-tree는 선택 받지 못했다.

 

그러면, 분명히 데이터를 찾을 때, O(logN) 시간보다 더 빠르게 값을 찾을 수 있는 자료구조 HashTable이 있을 때 왜 사용을 하지 않았을까?

 

인덱스를 사용할 때는 등호 연산만 있는 것이 아닌, 부등호 연산도 존재한다. B-tree는 정렬이 되어 있기 때문에, 부등호 연산에도 유리하다. 하지만, HashTable은 등호 연산에만 값을 찾아오는 것에 유리하기 때문에 인덱스로 사용하기 부적합하다!!!

 

결론은 한 노드의 넣을 수 있는 "데이터의 수"가 많고, "부등호 연산"도 가능한 B+tree를 사용한 것이다.

 

B+tree의 특징은 뭘까❓

최상단에 root node, 최하단 leaf node, 중간 노드들을 branch node라고 합니다. branch node들은 값을 가지고 있지 않고, 키에 대한 정보만 가지고 있습니다. 그래서 b-tree보다 더 많은 key를 저장할 수 있어, tree의 높이를 낮출 수 있습니다. leaf node끼리는 링크드 리스트를 통해 연결되어 있어, 부등호 연산을 할 때 유용하게 사용됩니다.

 

Index의 종류

Index는 clustered index와 non-clustered index로 나눌 수 있다.

 

클러스터 인덱스는 개발자가 설정하는 Index가 아닌 MySQL이 자동으로 설정하는 Index이다. Primary Key라고 하고, 보통 auto-increament를 걸어준다. 클러스터 인덱스만이 실제 테이블의 위치를 알고 있다. 그리고 실제 데이터들은 클러스터 인덱스 기준으로 저장되어 있다. 그래서 우리가 DataGrip으로 봤을 때, 기본적으로 PK로 정렬되어 있는 것을 볼 수 있을 것이다.

 

넌클러스터 인덱스는 개발자 또는 DBA등이 설정하는 모든 Index이다. 인덱스는 정렬이 되지만, 데이터는 정렬이 되지 않는다. 넌클러스터 인덱스의 leaf node에는 cluster index의 leaf node를 참조하고 있다!!

 

어떤 컬럼을 Index로 설정하는 것이 좋을까❓

"카디널리티"가 높은 컬럼을 Index로 설정하는 것이 좋다. 여기서 카디널리티란 컬럼의 중복된 수치를 나타낸다. 중복도가 낮으면 카디널리티가 높고, 중복도가 높으면 낮다. 최대한 많은 데이터가 걸러져야 찾아볼 데이터가 준다. 즉, 인덱스의 성능이 좋아진다. 

 

Reference

- https://kyungyeon.dev/posts/66?fbclid=IwAR39XBuRgImuzAhAXX272p_eEEcUZlz8fSpr8Sx_XX4FzHwaTHe8jlyMgPc

DB Index 동작원리를 알아보자

- https://helloinyong.tistory.com/296

데이터베이스 인덱스는 왜 'B-Tree'를 선택하였는가