[mysql/DB] 인덱스, B-Tree, Hash

728x90

인덱스 제일 공부를 하고 싶었던 것이다.

보통 성능 개선을 말할때 인덱싱을 걸거나 분산처리(샤딩, 파티셔닝, 레플리카, 페더레이션) 등 이 있다.

그 중 가장 중요한 인덱스에 대해 알아보려고한다.

인덱스란 보통 책 맨 뒤 "찾아보기" 를 언급한다. 책의 "찾아보기"와 , 인덱스 의 공통점은 정렬이다

DMBS 의 인덱스는 SortedList 처럼 저장되는 칼럼의 값을 이용해 항상 정렬된 상태를 유지하고.

데이터 파일은 ArrayList 처럼 순서대로 별도의 정렬없이 그대로 저장한다.

그럼 SortedList 의 장단점이 인덱스의 장단점이 될 수 있다.

항상 정렬 해야한다.
1. insert, update, delete 처리가 느리다
2. select 속도 엄청 빠르다.
이미 정렬 되어있어 원하는 값을 빠르게 가져올 수 있다.

select 쿼리의 where 조건절에 사용되는 칼럼이여도, 전부 인덱스로 생성하면 인덱스의 크기가 비대해져 오히려 역효과를 불러올 수 있다.

인덱스는 역할별로 구분하면 PK 와 보조키 (세컨더리 인덱스, Secondary key) 로 구분 가능하다.

대표적인 데이터 저장 방식 알고리즘

1. B-Tree 인덱스 (가장 일반적으로 사용되는 알고리즘)

이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조

칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘
B 는 이진을 나타내는 Binary 가 아니라 Balanced 이다
인덱스의 키 값은 모두 정렬돼 있지만. 데이터 파일의 레코드는 정렬 되어 있지않다.
- 데이터 파일의 레코드는 insert 가 된 순서대로 저장되지 않는다. 만약 insert만 수행한다면 맞지만, 레코드가 삭제되어 빈 공간이 생기면 그 다음의 insert는 가능한 삭제된 공간을 재활용 하게 된다.
B-Tree 키 추가
- 저장될 키 값을 이용해 적절한 위치를 탐색
- 그 위치를 리프 노드에 저장, 리프 노드가 꽉차면 리프노드가 분리 -> 상위 브랜치 노드까지 처리의 범위가 넓어 질 수 있다.
- 새로운 키를 추가하는 작업에 비용에 돈이 많이 든다.
- 테이블의 키를 추가하는 작업비용 1
  테이블의 인덱스 를 추가하는 작업비용: 1.5
인덱스는 페이지 단위로 관리된다 (디스크에 데이터를 저장하는 기본단위)

이렇게, 리프, 루트, 브랜치 하나하나를 페이지로 할 수 있다.

테이블에 1000만 건의 레코드가 저장 되어 있을때

그 중 500만건 버리기 VS 인덱스를 통해 필요한 500만건만 읽기 뭐가 더 좋을까?

옵티마이저는 인덱스를 통해 레코드 1건 읽는 것이, 테이블에서 직접 레코드 1건 읽는 것 보다 4~5배 정도 비용이 더 많이 든다고 한다.

즉 인덱스로 테이블 레코드의 20~25프로를 넘어서면 인덱스를 사용하지 않고 테이블을 모두 읽어 필요한 레코드만 가려내는 방식이 효율적이다.

이런 작업은 옵티마이저가 힌트를 무시하고 테이블을 직접 읽는 방식으로 처리한다.

인덱스 레인지 스캔 (한건, 한건 이상 읽는걸 통틀어서)

-> 검색하는 결과 레코드 건수와 관계없이 검색해야 할 범위가 결정됐을 때 사용하는 방식이다.

인덱스 풀 스캔

인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한 후 링크드 리스트 를 따라 처음부터 끝까지 스캔하는 방식

효율성:

인덱스 레인지 > 인덱스 풀 스캔 > 테이블 풀 스캔

B-Tree 인덱스의 효과를 얻으려면

이 경우를 제외해야 한다.

문서의 내용 전체를 인덱스화 해서 특정 키워드가 포함된 문서를 검색하는 전문 검색에는 B-Tree 인덱스를 사용할 수 없다

2. 클러스터링 인덱스 VS 비클러스터링 인덱스

클러스터링 인덱스

정의 : Cluster 인덱스는 키 값에 따라 테이블의 데이터 행을 정렬하는 인덱스 유형

테이블의 레코드를 비슷한 것들끼리 묶어서 저장하는 형태(InnoDB 에서만 지원)

- 테이블의 pk에 대해서만 적용되는 내용

- 테이블 당 하나만 가질 수 있다.

- 키 기반의 검색이 빠르다.

- 저장 키 변경이 상대적으로 느리다.

- B-Tree 와 비슷하지만, 세컨더리 인덱스를 위해 리프 노드에는 모든 칼럼이 같이 저장되어있다.

즉 클러스터링 케이블은 그 자체가 거대한 인덱스 구조로 관리된다.

- 기본적으로 pk 가 클러스터273링 키, 없으면 NOT NULL 의 UNIQUE INDEX, 없으면 자동으로 UK 값을 가지는 증가되 는 칼럼 추가한 후 클러스터링 키로 선택

import javax.persistence.Entity;
import javax.persistence.Id;

@Entity
public class User {
    
    @Id
    private Long id;
    
    private String name;
    private String email;
}

이렇게 걸면 ID로 클러스터링 인덱스가 생성이 된다.

어떻게 사용하냐 ??

ID로 찾으면 인덱싱 된 id로 값을 찾아오게 된다.

User user = userRepository.findById(1L).orElse(null);

비클러스터링 인덱스

테이블의 실제 데이터와 별도로 저장된다. 인덱스는 데이터 행의 위치를 가리키는 포인터를 가지고 있다.
하나의 테이블에 여러 개의 비클러스터링 인덱스를 생성할 수 있다. 각 인덱스는 특정 쿼리에서의 성능을 개선하는 데 사용된다.
기본 키(클러스터링 인덱스)와는 독립적으로 존재다다. 비클러스터링 인덱스는 기본 키와는 다른 컬럼에 대해 추가적인 인덱스를 생성한다.
데이터의 특정 컬럼에 대해 빠른 검색을 가능하다. 인덱스는 해당 컬럼의 값과 데이터 행의 위치를 매핑한다..
데이터의 순서를 보장하지 않는다. 인덱스는 컬럼의 값에 대한 정렬만 제공하며, 데이터 테이블의 물리적 순서에는 영향을 미치지 않는다.
별도로 저장되므로 디스크 공간을 추가로 사용한다. 데이터와 인덱스가 각각 별도로 저장되기 때문이다.

import javax.persistence.Entity;
import javax.persistence.Id;
import javax.persistence.Table;
import org.hibernate.annotations.Index;

@Entity
@Table(name = "user", indexes = @Index(name = "idx_name", columnList = "name"))
public class User {
    
    @Id
    private Long id;
    
    private String name;
    private String email;
}

이렇게 하면 name에도 인덱싱이 걸리게 된다.

3. Hash 인덱스