Index에 관해서

RDBMS의 Index란

Index, 우리가 책을 볼 때 가장 앞에서 목차를 보게된다. 그 때 각각의 항목들이 정렬돼서 원하는 주제의 내용페이지 (DB로 따지자면 특정 테이블의 데이터)를 손쉽게 찾게된다. DB도 마찬가지로 Index란 별도의 목차를 가지고 데이터를 접근하게 된다.

• Select문 즉 테이블의 검색속도를 향상시키기 위해 사용되는 메커니즘으로 별도의 저장공간에 정렬돼서 저장된다.
• Where, Order by, Join을 빈번하게 사용하는 테이블 혹은 컬럼일 경우 자주 사용된다.
• 자주 바뀌는 컬럼(Update, Insert, Delete)은 Index로 만들게 되면 오히려 성능이 저하될 수 있다.
• Index를 사용하게 되면 Full scan을 피할 수 있게 된다.
  • full scan은 이번 주제에 다루지 않겠지만, DBMS 성능에 큰 영향을 관여하는 탐색 메커니즘입니다. 추후에 이 주제로 별도로 포스팅 하겠습니다.

---

Index의 자료구조

BTree

• 자료구조 Balanced Tree(AVL,Red Black, Balance, 2-3, 2-3-4)중 Balance tree를 사용한 구조
• 평균 O(logN)이란 복잡도를 가지는 자료구조로써, 이진 탐색 트리의 최악의 복잡도O(N)을 개선한 자료구조.
• BTree구조상 하나의 노드에 여러 데이터가 저장되지만, Red Black tree의 경우엔 1개씩만 가질 수 있다.
• 각 노드들의 데이터들은 정렬된 상태이다.

---

B+Tree

• Btree의 확장 개념의 자료구조이다.
• B+Tree의 경우 BTree와 달리 중간노드(브렌치 노드)에 키값만 존재한다. -> 데이터는 리프 노드에 linked list처럼 연결되어 있다.
  • 이런 구조일 경우, Full scan시 Leaf 노드의 데이터를 순차적으로 확인하기 때문에 Leaf Node까지 가지 않아도 되는 BTree가 나아 보일수 있지만, 데이터베이스 검색 구조상 인덱스 컬럼은 부등호(<,>)를 이용한 순차 검색이 있기 때문에 탐색이 빨라집니다.(Linked List는 상수의 시간복잡도)
• Mysql InnoDB가 B+Tree구조를 사용한다.

https://stackoverflow.com/questions/870218/what-are-the-differences-between-b-trees-and-b-trees

---

BitMap

• 앞에서 살펴본 Btree, B+tree는 중복데이터가 적을경우 사용되지만, 데이터 값이 중복되는 경우(boolean 연산) BitMap Index를 사용 -> 예를 들어 성별 컬럼이 있다.
• 어떠한 데이터가 어디 있다라는 지도정보(Map)을 Bit(0,1)로 표시한다.
• 데이터가 변경될때 Btree의 경우 해당 노드만 수정해야 하지만, BitMap의 경우 Map전체를 수정해야 하는 overhead가 발생
• BitMap Index는 블록 단위로 Lock걸려 있기 때문에 블록에 들어 있는 다른 데이터가 수정이 발생하면 반영이 안될 경우도 종종 발생.

---

Hash Table

• Key값을 이용해 고유한 인덱스를(Hash Function을 이용해 생성된 index Key) 생성하는 방식
• 시간복잡도 O(1)를 가진 자료구조로써 키-값(Key,Value)을 가진 방식이다.
• 1:1 매칭으로 Key값을 이용해 데이터에 접근하지만 데이터베이스 특성상 부등호 연산(<,>)이 필요하기 때문에 자주 사용되지 않는 자료구조이다.

 

https://helloinyong.tistory.com/296

---

인덱스의 유형

Clustered index

• Clustered index는 테이블당 한개만 존재
• 루트 페이지와 리프 페이지로 구성되어 있으며, 리프 페이지는 데이터 페이지이다.
• 물리적으로 데이터가 정렬되어 있어 Non-Clustred Index보다 탐색이 빠르다. (반면 삽입, 수정, 삭제일 경우 느림-> 정렬되기 때문에)

이해를 쉽게 하기위해 다른 블로거가 설명한 Clustred Index방식을 참조하겠다. 참조한 사이트

https://velog.io/@gillog/SQL-Clustered-Index-Non-Clustered-Index

Clusterd Index는 물리적으로 행을 재배열 한다는 말은 데이터가 쌓이면 오른쪽 데이터 페이지(리프 페이지)에서 데이터가 쌓이게 된다(왼쪽 인덱스 페이지는 그대로) 만약 위의 그림에서 데이터 페이지 3번에 있는 차영일이란 컬럼을 select한다면 다음과 같은 동작이 일어난다.

1. 차영일의 인덱스 키값은 8이다.
2. 인덱스 8의 범위는 인덱스 페이지 7~10범위에 해당하므로 7이 참조하고 있는 데이터 페이지3번에서 해당 데이터를 찾게된다.

이러한 메커니즘은 물리적으로 행(데이터)가 정렬되어 있기때문에 가능하며, 범위 검색에 유용할 것이다.

---

Non-Clustered Index

• Non-Clustered Index의 경우 인덱스의 RID(Row ID)를 이용해 데이터 페이지를 참조(포인팅)하게 된다.
• 테이블당 여러개의 인덱스를 생성할 수 있게된다.(물리적으로 재배열 하지 않기 때문)

구조는 다음과 같이 구성된다. 

• 루트 페이지는 인덱스 페이지 7
• 중간 레벨의 페이지는 인덱스 페이지 (1,2,3,4)
• 실제 데이터 페이지는 맨 오른쪽(1,2,3,4,5)

https://velog.io/@gillog/SQL-Clustered-Index-Non-Clustered-Index

인덱스 ID가 10인 유병수를 찾는 흐름을 보면 다음과 같다.

1. 루트 페이지(인덱스 페이지7)에서 범위가 10인 인덱스 페이지 포인트를 찾게 된다.
2. 9<10<13이므로 인덱스 페이지 3번으로 간다
3. 인덱스 페이지 3번에서 인덱스 ID 10은 1-4-1이다.
4. 데이터 페이지 4번에서 첫 번째 행을 찾았다.

인덱스 페이지에서 데이터 페이지를 포인팅 할때 맨 앞의 숫자는 파일 그룹이라 가정하면 (ex 인덱스 페이지 1-3-1) 위와 같은 흐름이 나온다.

 

그렇다면 클러스터 인덱스와, 넌클러스터 인덱스를 같이 쓴다면 어떠한 그림이 나올까?

https://velog.io/@gillog/SQL-Clustered-Index-Non-Clustered-Index

여기서 주의할점은 넌클러스터드 인덱스 RID는 클러스터된 인덱스의 RID가 된다.

---

[REFERENCE]

https://velog.io/@gillog/SQL-Clustered-Index-Non-Clustered-Index

[SQL] Clustered Index & Non-Clustered Index

https://www.sqler.com/board_SQL2011/394701

개발자 커뮤니티 SQLER.com - [SQL2012강좌] 20. 클러스터드 인덱스와 넌 클러스터드 인덱스

https://helloinyong.tistory.com/296 

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