[DB] Index

인덱스란?

인덱스 == 목차, RDBMS에서 검색 속도를 높이기 위한 기술

인덱스는 결국 지정한 컬럼들을 기준으로 메모리 영역에 일종의 목차를 생성하는 것이다.

인덱스가 필요한 이유

컴퓨터는 자주 사용되는 데이터(테이블 등)를 메모리에 올리는데, 사용자가 데이터를 찾을 때 메모리에 데이터가 없다면 디스크에서 테이블 전체를 훑으면서 찾아야 하고 이를 Full Table Scan이라고 한다. 대용량 데이터에서는 굉장히 비효율적이다.

그래서 Full Table Scan을 방지하기 위해서 목차와 같은 인덱스를 만들어서 데이터를 관리한다. 

특징

인덱스의 구조 예시 (출처 : https://jojoldu.tistory.com/243)

• 인덱스는 메모리에 저장된다.
• B-Tree 형태로 저장됨 자식 노드가 2개 이상
• 디스크에 데이터를 저장하는 Page(Block)을 가장 기본단위 로 삼는다. 디스크 읽기 쓰기 작업의 최소단위.
• 인덱스도 페이지 단위로 관리되며, 그림상의 노드가 하나의 페이지를 의미한다.
• 인덱스는 Range Scan(리프 블록에서 스캔 시작 지점부터 중간에 찾고자 하는 노드를 찾으면 탐색을 멈춤)을 하는데 이는 Full Table Scan과 반대되는 개념이고며 더 효율적이게 된다.
• 약 10%의 추가 저장 공간 필요 

종류

Clustered

• 예) 책에서 바로 페이지를 아는 것
• 군집화 : 인덱스와 데이터가 연결된 형태
• 정렬되어 저장된다.
• 한 테이블에 하나만 존재할 수 있다.(중복 불가)
• 테이블의 PK에 대해서만 적용된다.(PK는 클러스터드 인덱스의 기준)
  • PK에 의해 레코드 저장 위치가 결정되며 PK값이 변경되면 물리적인 저장위치가 바뀌고 랜덤 액세스가 많이 발생하며 IO증가하기 때문에 PK를 신중하게 결정해야 한다.
• 범위검색에 강력 O(1)
• 논클러스터드 인덱스보다 빠르다.
  • Clustered index는 leaf node에 row data를 갖고 있기 때문에 Non-clustered index(secondary index)보다 access가 빠름
• 중간삽입하는 경우에 성능에 악영향

Non Clustered

• 예) 책에서 목차를 보는 것
• 비군집화 : 데이터와 연결되어있는 것이 아니라 다른 인덱스와 간접적으로 연결되어 있음.
  • Non Clustered index의 leaf node에는 row data에 접근할 수 있는 primary key가 저장되므로 두번의 access가 필요
  • primary key를 찾기 위한 access -> clustered index(대게 pk)를 이용하여 row data를 찾기 위한 access
• 정렬되어있지 않아서 데이터와 순서는 상관이 없음
• 데이터와도 관련 없음
• 한 테이블에 여러개 가능

 

인덱스 활용

구분	내용
SELECT	from, where 절이 있을 때 성능 향상
INSERT	오히려 성능을 저하시킬 수 있음. 인덱스는 정렬이 된 상태로 저장이 되어야 하고, 인덱스는 테이블과 별도의 객체라서 데이터를 테이블과 인덱스에 각각 삽입을 해야하기 때문에 낭비가 있을 수 있다.
UPDATE	오히려 성능을 저하시킬 수 있음. 인덱스에는 업데이트라는 개념이 없어서 테이블에 업데이트가 발생할 경우 DELETE 후 INSERT를 작업하기 때문에 부하가 크다.
DELETE	오히려 성능을 저하시킬 수 있음. 실제로 데이터를 지우는 것이 아니라 인덱스 안에 '사용안함'이라는 표시를 해주기 때문에 공간낭비가 있다.

insert, update, delete (Command)의 성능을 희생하고 대신 select (Query)의 성능을 향상시킨다.
여기서 주의할 점은 update, delete 행위가 느린것이지, update, delete를 하기 위해 해당 데이터를 조회하는것은 인덱스가 있으면 빠르게 조회가 된다.

인덱스가 없는 컬럼을 조건으로 update, delete를 하게 되면 굉장히 느려 많은 양의 데이터를 삭제 해야하는 상황에선 인덱스로 지정된 컬럼을 기준으로 진행하는것을 추천

따라서, 상황에 따라 상대적인것이기 때문에 무조건 인덱스를 쓴다고 효율적인 것은 아니다.

정리

사용하면 좋은 경우

• Where 절에서 자주 사용되는 Column
• 외래키가 사용되는 Column
• Join에 자주 사용되는 Column

Index 사용을 피해야 하는 경우

• Data 중복도가 높은 Column
• DML이 자주 일어나는 Column

 

인덱스 Column 설정 기준

Cardinality(기수성)가 높은 것

데이터를 분류할 기준을 선택할 때 '카디널리티'라는 개념이 등장한다. 카디널리티는 기수성 즉, 어느 그룹에 속하는 요소의 수를 의미하며 카디널리티가 높은 것이 바로 기준이 된다.

성별 < 닉네임 < 주민번호 

왼쪽에서 오른쪽으로 갈 수록 카디널리티가 높다.
주민번호는 고유값이기 때문에 사람 수 만큼 존재하기 때문에 어떤 기준보다도 카디널리티가 높다고 할 수 있다.

이렇게 카디널리티가 높은 값을 인덱스 컬럼 기준으로 삼아야 원하는 값을 쉽게 걸러낼 수 있다.

 

인덱스 구조

MySQL은 BTREE(B-Tree 및 B+Tree) 및 HASH 인덱스를 모두 사용한다.

B-Tree

대부분의 MySQL 스토리지 엔진의 기본 색인 구조

B-Tree는 노드가 inorder traversal에서 정렬되기 때문에 자체 균형 트리로 알려져 있다. B-트리에서 노드는 두 개 이상의 자식을 가질 수 있다(최대 M개의 자식, M차 B-Tree). B-Tree의 높이는 logM N이다(여기서 'M'은 트리의 차수이고 N은 노드 수).  

업데이트할 때마다 높이가 자동으로 조정된다. B-트리에서 데이터는 왼쪽이 가장 낮은 값, 오른쪽이 가장 높은 값으로 특정 순서로 정렬된다. B-Tree에 데이터나 키를 삽입하는 것은 이진 트리보다 복잡하다.

마지막으로 가장 자주 액세스하는 데이터가 루트 노드에 더 가까울 때 B-Tree가 더 잘 수행된다

특징

• 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있습니다.
• 노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있습니다.
• 노드의 키가 x개라면 자식의 수는 x+1개 입니다.
• 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족합니다.
  (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개입니다.)

검색, 삽입, 삭제 과정

[자료구조] 그림으로 알아보는 B-Tree

B+Tree

B+Tree 구조는 B 트리 구조와 유사하다.  InnoDB 스토리지 엔진은 B+Tree 구조를 사용하여 인덱스를 저장한다.

B+Tree는 데이터 포인터를 트리의 리프 노드에만 저장하여 인덱싱에 사용되는 B-트리의 단점을 제거한다. 따라서 B+ 트리의 리프 노드 구조는 B 트리의 내부 노드 구조와 상당히 다르다. 

여기서 유의할 점은 데이터 포인터는 리프 노드에만 존재하기 때문에 리프 노드에 액세스하려면 디스크 파일 블록에 대한 해당 데이터 포인터와 함께 모든 키 값을 반드시 저장해야 한다는 점이다. 

또한 리프 노드는 연결리스트의 형태를 띄고 있다. B-Tree는 리프 노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+Tree는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 줄어든다.

리프 노드의 키 값 중 일부는 내부 노드에도 나타나 단순히 레코드 검색을 제어하는 ​​매개체 역할을 한다.

특징(B-Tree와 동일)

• 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있습니다.
• 노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있습니다.
• 노드의 키가 x개라면 자식의 수는 x+1개 입니다.
• 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족합니다.
  (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개입니다.)

검색, 삽입, 삭제 과정

[자료구조] 그림으로 알아보는 B+Tree

B-Tree vs B+Tree

S.NO	B-Tree	B+Tree
1	모든 내부 및 리프 노드에는 데이터 포인터가 있다.	리프 노드에만 데이터 포인터가 있다.
2	모든 키를 리프에서 사용할 수 없기 때문에 검색에 더 많은 시간이 소요되는 경우가 많다.	모든 키는 리프 노드에 있으므로 검색이 더 빠르고 정확하다.
3	트리에서 키의 복제가 유지되지 않는다.	키의 중복이 유지되고 모든 노드가 리프에 있다.
4	삽입하는 데 시간이 더 걸리고 예측할 수 없는 경우가 있다.	삽입이 더 쉽고 결과는 항상 동일합니다.
5	내부 노드의 삭제는 매우 복잡하고 트리가 많은 변형을 거쳐야 한다.	모든 노드가 리프에서 발견되기 때문에 모든 노드의 삭제가 쉽다.
6	리프 노드는 구조적 연결 목록으로 저장되지 않는다.	리프 노드는 구조적 연결 목록으로 저장된다.
7	중복 검색 키가 없다.	중복 검색 키가 있을 수 있다.

Hash

데이터를 찾는데 사용되는 키-값 세트가 있고, 해시 함수는 실제 데이터 버킷이 저장된 주소를 계산하는데 사용된다. 그러면 키-값과 관련된 레코드의 위치가 표시된다.

값은 해시 함수의 값을 기반으로 버킷에 저장된다. 값을 검색하려면 해시 함수를 사용해 버킷 주소를 계산하고, 찾으면 끝. 찾지 못하면 인덱스에 없다는 의미다.

새 값을 추가하는 것도 유사하게 동작한다.

 

참고

• www.youtube.com/watch?v=9ZXIoh9PtwY
• www.youtube.com/watch?v=NkZ6r6z2pBg
• jojoldu.tistory.com/243
• pearlluck.tistory.com/54
• https://gyoogle.dev/blog/computer-science/data-base/Index-.html
• https://www.vertabelo.com/blog/all-about-indexes-part-2-mysql-index-structure-and-performance/
• https://www.geeksforgeeks.org/difference-between-b-tree-and-b-tree/
• https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree