INDEX
INDEX는 데이터베이스에서 릴레이션의 검색 성능을 높여주는 대표적인 방법 중 하나이다. 일반적인 RDBMS에선 B+Tree 자료 구조를 사용하여 구현한다.
INDEX 방식은 테이블의 컬럼을 별도로 저장하여 검색 시 해당 테이블의 레코드를 FULL SCAN하는 것이 아니라 INDEX 파일을 검색하여 검색 속도를 빠르게 한다. SEARCH-KEY라는 이름의 속성값과 포인터를 통해 검색하여 SELECT 결과를 빠르게 찾아올 수 있다.
클러스터형 인덱스
- 기본키는 자동으로 클러스터형 인덱스가 생성된다. 해당 컬럼 기준으로 정렬이 된다.
보조 인덱스
- 보조 인덱스(secondary index)는 별도의 공간에 인덱스가 생성되며
create index와 같이 index를 생성하거나 고유키(unique)로 지정하면 보조 인덱스가 생성된다.
인덱스 장점
검색 속도 향상의 장점이 있다. FULL SCAN의 시간을 B+Tree - O(logN)으로 처리할 수 있다.
인덱스 단점
인덱스의 단점으로는 저장 공간 소모, 데이터 변경 문제로 크게 두 가지가 있다.
인덱스를 생성하기 위해서 추가적인 저장 공간이 필요하게 되는데, 이 공간은 보통 테이블 크기의 10%를 차지한다. 또한 인덱스는 SELECT문에서 WHERE절에 있는 값을 빠르게 가져올 수 있지만 데이터를 변경하는 경우 성능이 나빠질 수 있다. 그 이유는 데이터가 추가, 삭제 될 때마다 tree의 구조가 변경(매번 정렬)될 수 있기 때문이다.
인덱스 컬럼 선택
인덱스 컬럼을 지정할 때 카디널리티, 선택도, 조회 활용도, 수정 빈도 등을 판단해서 선택하는 것이 중요하다.
카디널리티 : 데이터가 중복되지 않는 정도
선택도 : 데이터가 선택되는 정도 (카디널리티와 반대)
조회 활용도 : WHERE 절에서 사용되는 횟수
수정 빈도 : 컬럼이 변경되는 빈도
B+tree
인덱스 기능을 사용할 때 Hash table을 사용하면 O(1)로 가능하지만, B+Tree는 O(logN)이 걸린다. 그럼에도 B+Tree를 사용하는 이유는 Hash의 경우 값이 정렬되어 있지 않기 때문에 범위를 가져오는 쿼리에는 매우 비효율적이기 때문에 데이터를 정렬하는 B+Tree가 유리하기 때문이다.
- 다음과 같이 인덱싱이 적용된 테이블을 보고 B+트리로 나타내보자.
먼저 M차 B트리의 규칙을 살펴보자
- 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다.
- 노드에는 최대 M-1개부터 [M/2] - 1 개의 키가 포함될 수 있다.
- 노드의 키가 X개라면 자식의 수는 X+1개여야 한다.
- 최소차수는 자식 수의 하한 값을 의미하며, 최소차수가 t라면 M = 2t - 1을 만족한다.
- B+ 트리는 각 KEY값과 DATA 값이 존재한다.
- B트리와 다른 점
- B트리는 리프노드가 아닌 각자 key와 data를 가지지만, B+트리는 리프 노드에 모든 data를 갖는다.
- B트리는 옆 리프노드를 탐색할 때 루트부터 출발해야하지만, B+트리는 모든 리프노드가 연결리스트의 형태를 띄고 있어 선형적으로 탐색할 수 있다.
REFERENCES
