Index
데이터베이스에서의 인덱스란 데이터를 빠르게 찾을 수 있는 데이터 구조로, RDBMS에서 검색 연산의 속도를 높이기 위한 방법이다.
책 맨 뒷장에 있는 찾아보기처럼 내가 원하는 데이터가 DB의 어디에 저장되어있는지 빠르게 찾을 수 있다.
데이터베이스의 파일 구조에는 인덱스 이외에도 순차 방법과 해싱 방법이 있지만, 순차 방법은 물리적 순서와 논리적 순서를 동일하게 유지해야 하기 때문에 융통성이 떨어지고 탐색 시간이 오래 걸린다는 단점이 있다.해싱 방법은 등호 연산(=)을 사용할 때는 O(1)로 굉장히 빠르지만, 부등호 연산(>, >=, <, <=)에는 적합하지 않기 때문에 잘 사용하지 않는다.
인덱스의 특징
- 기본키 컬럼은 자동으로 인덱스 생성됨
- 데이블의 컬럼에 인덱스가 없는 경우, 테이블의 전체 내용을 검색(Table Full Scan)
- <키값, 주소> 쌍으로 구성
B-Tree
인덱스는 보통 B-Tree라는 트리 자료 구조로 이루어져 있다.
이진트리를 확장해서 하나의 노드가 2개 이상의 자식 노드를 가질 수 있는 트리 구조이다.
각 노드는 여러 개의 Key를 갖고 있고, 각 Key에 대응하는 Data도 함께 갖고 있다. 항상 Key를 기준으로 오름차순 정렬되어 각 노드에 배치된다.
이진 탐색에서 왼쪽 자식 노드의 Key는 자신보다 작고, 오른쪽 자식 노드의 Key는 자신보다 큰데, B-Tree에서도 각 Key에 대해서 유사한 규칙이 적용된다.
B-Tree는 균형 트리(Balanced Tree)로서, 최상위 루트 노드에서 리프 노드까지의 거리가 모두 동일하다. 따라서 평균 탐색 시간 복잡도가 O(logN)이라는 장점이 있다.
B-트리는 루트 노드, 리프 노드, 그리고 이 두 노드 사이에 있는 브랜치 노드로 나뉜다.
B+ Tree
B+ Tree는 B-Tree를 개선한 자료구조이다. B-Tree의 특징과 대부분 유사하지만 가장 큰 차이점은 브랜치 노드(내부 노드)에는 key값만 저장되고 리프 노드에 key와 data를 함께 저장한다는 것이다.
이렇게 하면 브랜치 노드에는 data를 저장할 필요가 없어지기 때문에 상대적으로 적은 용량을 소비한다는 장점이 있다. 또한, data가 저장될 공간에 추가 key를 저장할 수도 있으므로 평균 트리의 높이가 낮아질 수 있다는 장점도 있다. 따라서 일반적으로 인덱스에는 B+Tree가 사용된다.
인덱스를 사용할 때 고려해야 할 사항
인덱스를 사용하면 데이터의 빠른 검색이 가능하다는 장점이 있지만, 항상 최신 상태로 정렬되어야 하기 때문에 데이터 갱신(INSERT, UPDATE, DELETE) 작업에 대해 추가적인 연산이 발생한다. 따라서 데이터 갱신보다는 조회에 주로 사용되는 컬럼에 인덱스를 생성하는 것이 유리하다.
인덱스를 사용하면 좋은 경우
- where 절에서 자주 사용되는 Column
- 외래키에 사용되는 Column
- Join에 자주 사용되는 Column
인덱스를 피해야 하는 경우
- 데이터의 중복도가 높은 Column
- 삽입, 삭제, 수정 연산이 자주 일어나는 Column
References
'CS > 데이터베이스' 카테고리의 다른 글
| NoSQL (0) | 2022.12.05 |
|---|---|
| Statement vs PreparedStatement (0) | 2022.12.03 |
| 데이터베이스 (0) | 2022.11.14 |