Full Table Scan
SELECT *
FROM users
WHERE username = 'tony';이 쿼리는 users 테이블 내 존재하는 모든 데이터 중 username 컬럼 값이 tony인 데이터를 반환
만약 username 컬럼에 인덱스를 사용하지 않았다면 해당 테이블을 처음부터 조건에 맞는지 하나하나 확인하게 된다.
이것을 Full Table Scan이라고 하며, 테이블 내 데이터가 많으면 많을수록 비용이 커지고 성능이 저하되게 된다.
인덱스(Index)란?
인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료구조이다.
예시로 주변에서 인덱스를 볼 수 있는데 책의 맨 뒤에 색인을 추가하여, 원하는 내용을 빠르게 찾을 수 있도록 도와준다. 이처럼 데이터베이스의 index는 책의 색인과 같은 역할을 한다.
즉, 데이터베이스의 인덱스는 추가적인 저장 공간에 정렬된 컬럼 사본을 사용하여 테이블 검색 속도를 향상 시키는 자료구조로 주로 B-Tree를 사용한다. (인덱스의 크기는 굉장히 작음)
인덱스는 SELECT 쿼리의 WHERE절을 사용되는 컬럼에 대한 조회 성능을 향상시킨다.
인덱스 형태
위 사진을 보면 Empno의 인덱스 명을 EmpnoIndex라고 하며, 각 Pointer는 EMPLOYEE에 맞는 EMPNE를 가리킨다. 그리고 EmpnoIndex는 정렬된 것을 볼 수 있다.
인덱스 알고리즘
1 ~ 100 중 숫자 하나를 맞추라고 할 때 주로 2가지 접근 방법이 있다.
- 1부터 100까지 순서대로 물어보는 경우
⇒ 이렇게 물어보면 최악의 경우 100번째일수도 있으므로 O(n)이 걸린다. - 중간 값을 부른 후 업 다운으로 물어보는 경우
⇒ 정렬된 경우 절반씩 소거하면 O(log n)이 걸린다.
이러한 방식을 이진탐색트리로 표현이 가능하다.
Binary Search Tree
균형 있는 이진탐색트리
시간 복잡도 : O(log n)
균형 없는 이진탐색트리
시간 복잡도 : O(n)
이진탐색트리를 사용하면 위처럼 최악의 경우 O(n)의 시간이 필요하기 때문에 성능이 매우 나빠질 수 있다.
B-Tree (Balanced Tree)
이진탐색트리의 단점을 극복하기 위해 B-Tree가 나왔다. (O(log n)의 시간복잡도를 가짐)
B-Tree는 자식 노드를 2개 이상 가질 수 있으며 트리의 높이가 같다는 특징이 있다.
인덱스와 실제 데이터가 저장된 데이터는 따로 관리가 된다.
인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있다.
60, 70, 75, 51, 52, 65, 68, 77, 78, 79
위 숫자들을 다음 B-Tree 생성 사이트에서 직접 생성해보자 (CRUD)
데이터베이스 인덱스에서 B-Tree를 사용하는 이유
⇒ 해쉬 테이블은 key-value로 시간복잡도가 O(1)이지만 정렬되어있지 않고 DB에서 데이터 찾을 때 범위로 찾기 때문에 (부등호 <,>연산) 해쉬 테이블 적합하지 않아서 B-Tree 사용
B+Tree
B+Tree는 B-Tree를 개선시킨 자료구조로, MySQL 등 많은 DBMS에서 사용한다.
B+Tree는 오직 리프 노드의 키만 데이터 포인트를 가지고 있어서 노드에 더 많은 키를 보관할 수 있다. 즉, 트리의 높이가 낮아지는 것을 의미하고, 탐색 속도가 B-Tree에 비해 더 향상된다.
이런 특징으로 트리에 중복된 키가 존재할 수 있다.
또한 B-Tree와 다르게 순차 검색에 유리하다. B-Tree는 트리 순회를 해야하기 때문에 부등호 연산이 오래 걸리지만, B+Tree는 리프 노드를 연결 리스트로 연결되어 있기 때문에 정렬된 상태의 리프 노드를 순차 검색할 수 있다.
60, 70, 75, 51, 52, 65, 68, 77, 78, 79
위 숫자들을 다음 B+Tree 생성 사이트에서 직접 생성해보자 (CRUD)
인덱스는 무조건 좋은가?
인덱스는 조회 성능을 개선하기 위해 저장 공간을 사용하게 되는데 이 공간은 데이터 베이스 전체 공간의 약 10%라고 한다. 즉, 불필요한 사용은 저장 공간을 낭비할 수도 있다.
조회 성능은 향상되지만, 생성/수정/삭제 작업에 대한 성능은 오히려 낮아진다. 따라서 조회보다 생성/수정/삭제 작업이 더 많이 발생한다면 오히려 성능이 저하될 수 있다. (데이터가 변경되면 다시 정렬)
인덱스 적용 기준
카디널리티가 높은 컬럼 (= 중복도가 낮은 컬럼)
카디널리티란 데이터 집합에서 유일한 데이터의 개수를 의미한다.
즉, 중복된 요소가 적은 컬럼이다. (데이터의 다양성이 높다)
여기서 카디널리티로 사용할 컬럼은 id, 이메일을 사용할 수 있다.
조건 검색 Join, Where절
조건절이 없다면 인덱스가 사용되지 않는다.
인덱스 테이블은 정렬되어 저장되어 있기 때문에 조건(where)에 맞는 데이터를 빠르게 찾을 수 있다.
정렬 Order by절
인덱스를 사용하면 Order by에 의한 Sort 과정을 피할 수 있다.
Order by는 데이터 정렬을 하기 때문에 부하가 굉장히 많다. 하지만 인덱스를 사용하면 이미 정렬되어 있기 때문에 비용 소모 없이 원하는 데이터를 가져올 수 있다.
MIN, MAX
데이터가 정렬되어있기 때문에 MIN값과 MAX값은 레코드의 시작값과 끝 값만 가져오면 된다.
Insert / Update / Delete가 자주 발생하지 않는 컬럼
- Insert : 새로운 데이터에 대한 인덱스를 추가
- Delete : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 (실제 삭제 x)
- Update : 기존 인덱스를 사용하지 않음 처리 후 갱신된 데이터에 대해 인덱스 추가
규모가 큰 테이블
