Clustered & Non-Clustered Index

Index

테이블 특정 데이터로 바로 접근할 수 있게 한 자료구조

주로 해시 테이블이나 B-tree, B+ tree로 구현된다

 

1)해시테이블

찾으려는 데이터를 input으로 얻은 해시값 = 데이터가 저장된 물리적 주소

별도의 저장 공간이 필요하지 않고, 등호 연산의 경우 시간 복잡도 O(1)로 매우 빠르다.

하지만 데이터가 정렬되어있지 않아 부등호 연산엔 효과가 없어서 DBMS에선 잘 쓰지 않는다.

 

 

2)B-tree

트리인 만큼 O(logN)으로 괜찮은 시간 복잡도를 지니고 있고

해당 노드보다 작은 key 값은 왼쪽에, 큰 값은 오른쪽에만 존재해 range search에 유리하다.

*MySQL은 index로 B-tree를 사용한다.

 

3)B+ tree

b+tree는 b-tree의 개선 버전으로,

모든 데이터가 leaf 노드에 연결리스트로 저장되어 있어

range scan 뿐 만 아니라 full scan에도 유리하다.

 

상위 노드는 data 없이 key와 pointer만 존재하므로 

상위 노드에 더 많은 key를 = 트리의 높이가 낮아 fanout이 높음

 

 

 

이와 같이 index는 데이터베이스의 검색 속도를 향상시키지만

추가적인 index 처리 작업을 필요로 하므로

데이터베이스의 insert, update, delete가 적고

where, join, order by가 많을수록 유리하다

 

https://khs20010327.tistory.com/115

B-tree와 B+tree (+ ISAM tree, Bulk Loading)

b-tree와 b+tree 자체에 대해선 따로정리

 

 

 

 

 

 

Clustered index & Non-Clustered index

 

 

Clustered index & Non-Clustered index

쉽게 말해 clustered index는 물리적으로 정렬된 index,

non-clustered index는 논리적으로 정렬된 index이다.

Clustered index는 data entry와 data record가 동일하다.

논리적으로도, 물리적으로도 정렬되어 있어 range search나 full table scan이 매우 빠르지만

데이터를 물리적으로 정렬해야하므로 데이터의 업데이트가 잦다면 성능이 떨어진다.

 

한 column에 대해서만 "물리적"으로 정렬될 수 있으므로 clustered index는 한 테이블에 하나만 존재 가능하다.

항상 그렇진 않지만 primary key = clustered index로 생각하면 쉽다.

 

 

 

 

 

 

 

 

 

 

 

https://rebro.kr/167

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등

인덱스에 대한 전체적인 개념과 장단점이 잘 적혀있음

 

https://helloinyong.tistory.com/296

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

해시 테이블과 b-tree 뿐만 아니라,

RedBlack-Tree, 배열, 연결리스트에 관해서도 상세히 설명되어있다.

 

https://stackoverflow.com/questions/37731060/range-queries-using-b-trees-and-b-trees

Range queries using B trees and B+-trees

스택 오버플로우 하나쯤 넣어야 간지날것같아서 추가

 

https://gwang920.github.io/database/clusterednonclustered/

Clustered vs NonClustered (index 개념)

clustered index에 대한 설명