데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 도구
테이블의 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장한다. (물리적 주소와 컬럼의 값 - key, value의 한 쌍)
장점: 테이블 검색 속도 및 성능 향상 ⇒ 시스템 전반적인 부하 감소
인덱스에 의해 데이터들은 정렬된 형태를 갖는다. Where문으로 특정 조건의 데이터를 찾기 위해서 테이블의 전체를 조건과 비교해야 하는 풀 스캔 작업과 비교해서, 인덱스는 데이터들이 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있다.
⇒ ORDER BY, MIN/MAX 역시도 이미 정렬되어 있기 때문에 빠르게 수행 가능
단점
- 인덱스를 관리하기 위한 추가 작업 필요
- 추가 저장 공간 필요
- 잘못 사용하는 경우 외려 성능 저하
인덱스를 항상 정렬된 상태로 유지해야 하기 때문에 인덱스가 적용된 컬럼에 삽입, 삭제, 수정 작업을 수행하면 추가 작업이 필요하다. (인덱스의 추가도 추가적으로 필요)
인덱스의 수정이 필요할 때는 기존의 인덱스를 사용하지 않는다는 작업을 수행하고 새로운 인덱스를 추가함.
⇒ 수정 작업이 많은 경우 실제 데이터에 비해 인덱스가 과도하게 커지는 문제점 발생 (추가 저장 공간 많이 필요)
전체 데이터의 10~15% 이상의 데이터를 처리하거나, 데이터의 형식에 따라 성능 낮아질 수 있음. (나이나 성별 같이 값의 범위가 적은 컬럼의 경우, 인덱스를 읽고 나서 다시 많은 데이터를 조회해야 하기 때문에 비효율적이다.)
인덱스를 사용하면 좋은 경우
데이터의 범위가 넓고 중복이 적고 조회가 많거나 정렬된 상태가 유용한 컬럼에 사용하는 것이 좋다.
Clustered Index : MySQL이 자동으로 설정하는 Index
- 해당 테이블에 Auto increments 값으로 Primary Key가 있다면 해당 컬럼이 Clustered Index
- 없다면, 컬럼 중에 Unique 컬럼이 Clustered Index
- 없다면, MySQL이 내부적으로 Hidden Clustered Index Key (row ID)를 만들어 사용
위 세 가지 경우의 공통점은 ?
⇒ count(*)와 distinct key한 값이 동일하다는 것.
⇒ 그 이유는 모든 row를 통틀어 중복이 적으면 적을수록 Index는 높은 효율을 자랑한다.
Non Clustered Index : 개발자가 설정하는 모든 Index
멀티 컬럼 Index의 경우 최대 16개의 컬럼을 사용할 수 있고, 테이블 당 인덱스의 개수는 최대 64개까지 지정이 가능 (Clustered Index까지 65개)
⇒ 멀티 컬럼 인덱스는 단일 컬럼 인덱스보다 비효율적이기 때문에 사용에 신중해야 한다.
Index를 설정했지만 Full scan으로 동작하는 경우
- 컬럼의 가공
- index로 설정된 컬럼의 값을 알고 있다해도 가공된 컬럼 값은 알 수가 없다. 때문에 우항에 연산을 옮겨야 한다.
- 부정형 (! =)
- 부정형의 경우 해당 데이터를 제외한 모든 데이터를 검색하라는 뜻이기 때문에 풀스캔
- like 앞 %
- B+Tree는 데이터의 첫 글자를 기준으로 정렬하기 때문에
- count(*)
- 개수는 모든 데이터를 다 돌아야만 알 수 있다.
자료구조
- 해시 테이블 : key와 value를 한 쌍으로 데이터를 저장하는 자료구조
(key, value)로 쌍을 표현하며, key값을 이용해 대응되는 value값을 구하는 방식.
해시 충돌이라는 변수를 제외하면 O(1)의 매우 빠른 시간만에 데이터를 탐색할 수 있다.
그렇지만, Index에서 해시 테이블은 사용되지 않음. why ?
⇒ 해시 테이블은 등호 연산에 최적화되어 있다. 데이터베이스에서는 부등호 연산이 자주 사용되기 때문에.
- B- Tree : 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 Balanced Tree의 일종
모든 leaf node가 같은 level로 유지되도록 밸런스를 맞춘다.
자식 node의 개수가 2개 이상이며, node 내의 key가 1개 이상일 수 있다.
-
node의 key 수가 k개라면, 자식 node의 수는 k+1개
-
node의 key는 반드시 정렬된 상태
-
자식 node들의 key는 현재 node의 key를 기준으로 크기 순으로 나뉘게 됨.
-
root node는 항상 2개 이상의 자식 node를 가짐 (root node = leaf node 제외)
노랑 : 자식 node를 가리키는 포인터
숫자 담긴 네모 : key
숫자 : data(value)
B-Tree의 탐색
B-Tree의 삽입
- key의 개수 / 2 + 1 번째 값을 올림
B-Tree의 삭제
- 삭제할 key가 leaf node에 있는 경우
- 현재 node의 key 수가 최소보다 큰 경우 (14)
- 현재 node의 key 수가 최소이고, 왼쪽 또는 오른쪽 형제 node의 key수가 최소보다 큰 경우 (10)
- 삭제할 위치를 Parent로 바꿈
- 왼쪽 형제 node의 key 수가 최소보다 크다면 Lmax로, 오른쪽에서 그렇다면 Rmin으로 Parent.
- 현재 node와 왼쪽, 오른쪽 형제 node의 key수가 최소, 부모 node의 key 수가 최소보다 큰 경우 (16)
- 값을 삭제하고 parent를 부모 node에서 분할하여 형제 node와 병합
- 현재 node와 왼쪽, 오른쪽 형제 node, 부모 node 모두 key 수가 최소인 경우
- 하단 설명(현재 node와 자식 node 모두 key 수가 최소인 경우)과 동일
- 삭제할 key가 leaf node를 제외한 node에 있는 경우
- 현재 node 또는 자식 node의 key수가 최소보다 큰 경우 (15)
- K의 Lmax또는 Rmin과 자리를 바꾸고 삭제
- 현재 node와 자식 node 모두 key 수가 최소인 경우 (4)
- 트리를 재구조화해야한다.
- K를 삭제, K의 양쪽 자식을 하나로 합친다 (a)
- K의 parent를 K의 형제 node에 병합 (b)
- a를 b의 자식이 되도록 연결
- b의 key 수가 최대보다 크면 key 삽입 과정과 동일하게 분할
- b의 key 수가 최소보다 작다면 a생성 이후부터 동일 과정 반복
- 현재 node 또는 자식 node의 key수가 최소보다 큰 경우 (15)
- B+ Tree : 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장
leaf node끼리는 Linked list로 연결되어있다.
B- Tree는 어느 한 데이터 탐색은 효율적이지만, 모든 데이터 순회에는 모든 노드를 방문해야하므로 단점을 개선
leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리 확보, 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 낮아짐, 검색 효율
풀스캔의 경우 B+Tree는 leaf node에만 데이터가 저장되고 연결리스트로 연결되어 있기 때문에 선형 시간 소모, B-Tree는 모든 노드 확인
반면, B- Tree는 최상의 경우 특정 Key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 leaf node까지 가야함.
B+ Tree의 삽입
B+ Tree의 삭제
- B- Tree의 경우와 동일하나 B+ Tree는 leaf가 아닌 node에 중복값이 존재하기 때문에 해당 key를 노드보다 오른쪽에 있으면서 가장 작은 값으로 바꿔주어야 한다.
B+ Tree의 수정
- 삭제 후 삽입
