📝인덱스 vs 클러스터링 인덱스
클러스터링 인덱스는 인덱스와 데이터가 하나로 결합된 B+Tree구조로 테이블 형태에 "키"로 인덱스가 들어가고 "값"으로 해당 키에 해당하는 데이터가 들어가게 됩니다.
한 테이블에 한개만 들어가기 때문에 보통 PK로 만들어지며 없으면 Unique + Not Null이고 그 이후에도 없으면 숨겨진 Row ID로 사용합니다. (MySQL은 이렇고 다른 RDBMS는 그에 따라 다름)
테이블 단위에서 관리하는 인덱스입니다.
인덱스의 경우는 먼저 포인터로 이동하면서 해당 위치를 찾은 이후에 데이터를 읽는 과정인데 클러스터링 인덱스의 경우 테이블형태로 바로 찾아가기 때문에 속도가 더 빠릅니다.
(성능은 단건 조회의 경우 40~50%이고 범위 조회일 경우 30~40%이고 대량 조회일 때는 35%가량 빠릅니다.)
📝힙 테이블
클러스터형 인덱스가 없는 테이블로 데이터가 아무 순서 없이 저장 됩니다. (삽입 순서대로 저장) 그렇기 때문에 저장하는 기능은 빠르지만 조회에 성능 문제가 있습니다.
📝Auto Increment vs Sequence
- Auto Increment
- 테이블의 특정 컬럼(PK 등)에 값이 없을 때 자동으로 1씩 증가하는 기능
- 테이블 단위에서 관리합니다.
- DB가 자동으로 다음 값을 넣어줍니다.
- 매우 사용하기 쉽지만 테이블간 공유가 되지 않아 병렬 대량 처리에는 미흡합니다.
- MySQL, SQL Server에서 이용
- Sequence
- 독립적인 객체로 호출할 때마다 증가값을 반환합니다.
- 여러 테이블에서 공유가 가능하며 증가값 세밀한 설정이 가능합니다.
- DB에서 자동적으로 넣어주지 않기 때문에 NEXTVAL을 이용해 다음 값을 가져와서 수동처리해야합니다.
- 병렬이나 대량 처리에 좋습니다.
- Oracle, PostgreSQL에서 이용
📝단일 인덱스, 복합 인덱스
CREATE INDEX idx_user_name ON users(name);단일 인덱스의 경우 단일 컬럼에 대해 인덱스 생성을 의미한다.
CREATE INDEX idx_user_name_age ON users(name, age);복합 인덱스의 경우 두가지 이상의 컬럼에 대해서 인덱스를 생성하는데 name, age 순서대로 where절을 사용해야 최적화 되어 사용된다.
name의 경우 단일 인덱스처럼 동작하지만 name을 통해 age를 찾기 때문에 age의 경우는 불가능하다. 그렇기 때문에 단일로 또 만드는게 낫다
📝카디널리티
카디널리티는 전체 행에 대한 특정 컬럼의 중복 수치를 나타내는 지표로 주민등록번호의 경우 PK로 사용이 가능하기 때문에 카디널리티가 높다고 할 수 있다. (즉, 중복이 없다는 뜻)
📝ISAM
ISAM은 순차적 접근 방법을 기반으로 하는 색인 방법 중 하나입니다
기본 아이디어는 데이터를 순차적으로 저장하면서 인덱스를 사용하여 특정 레코드를 빠르게 찾을 수 있도록 하는 것입니다 주로 정렬된 데이터 집합에서 사용되며 ISAM은 기본적으로 키─포인터 쌍을 가진 인덱스를 사용합니다
이 인덱스는 트리 형태로 구성되어 있어 검색이 빠르게 이루어집니다
순차 접근 액세스에 특화되어있기 때문에 검색 범위에 빈틈 없는 경우 더 효과적이다 예를 들면 1, 2, 3, 4, 5의 데이터가 있는 경우 1, 5를 가져오는 범위 쿼리보다는 1, 2, 3, 4 의 데이터를 가져오는 범위쿼리에 더 적합하다
ISAM의 경우 정렬 인덱스와 정적이면서 오버플로우 영역을 사용하기 때문에 성능 저하와 확장성 문제로 B-Tree를 더 많이 사용합니다.
📝B 트리 (B -Tree)
- 리프의 높이가 동일한 트리 형태 구조로 루트 노드, 리프 노드, 브랜치 노드 모두 데이터 저장 가능합니다.
- 노드당 자식의 수는 여러개로 최대 차수만큼 들어갑니다. (한 노드가 가질 수 있는 최대 자식 수를 차수라고 함)
- 그림에서의 4의 차수는 2개
- 데이터인 "키"는 최대 (최대 차수 - 1)만큼 들어가게 됩니다. (팬아웃 : 한 노드가 가질 수 있는 노드의 수)
- 루트 노드의 "키"는 7, 15인것이고 2가지의 "키"를 통해 1~7 | 7~ 14 | 15 ~ 영역으로 나뉩니다.
- 총 N개 데이터가 있으면 N개의 노드가 있게 됩니다.
- 오름차순으로 저장된 형태입니다.
- 트리가 높이가 낮아 여러 노드를 찾을 필요 없어 다른 거에 비해 안정적입니다.
- 삽입 / 삭제에 대해서는 다시 순서를 재배열해야하기 때문에 시간이 오래걸립니다.
- 시간복잡도는 아래와 같습니다.
📝B+ 트리 (B+Tree)
- B 트리를 개선시킨 것으로 리프 노드에만 데이터가 들어가있습니다. (모든 리프 노드가 연결 리스트로 되어있어 범위 검색에 특화 된 형태)
- 삽입 / 삭제에 대해서는 B-Tree하고 유사합니다.
📝이진 트리
트리의 자식 노드가 최대 2개만 가집니다.
이진트리를 사용하지 않고 B-Tree를 사용하는 이유는 팬아웃을 늘려 높이를 줄여 탐색하는데 시간을 줄여줍니다.
🔗 참고 및 출처
https://chamdom.blog/binary-tree/
https://hudi.blog/db-index-and-indexing-algorithms/