db 인덱스

2022.11.07 - [데이터베이스] - [MySql] 효과적인 인덱스 설계

[MySql] 효과적인 인덱스 설계

옛날에 작성한 글에서 조금 더 상세히 인덱스에 관해서 작성하기 위해서 

 

인덱스를 사용하는 이유는 인덱스 구조를 알면 알 수 있었다.

 

인덱스는 해시 테이블, B-Tree, B+Tree 로 주로 구현한다고 합니다.

인덱스를 생성하면 특정 컬럼(속성)의 값을 기준으로 정렬하여 데이터의 물리적 위치 주소와 함께

별도 파일에 저장합니다.

 

해시 테이블

해시 테이블은 key, value 형태로 데이터를 저장한다. key를 통해 값에 바로 접근하므로 검색 시 O(1)의 복잡도로 빠르게 데이터를 찾을 수 있다.

하지만 key의 등호 연산에만 유리하고 쿼리에서 자주 사용되는 부등호 연산에는 불리하다고 합니다..

B-Tree

B-Tree에 대해 알아보기 전에 왜 데이터베이스에서 일반적인 Tree가 아닌 B-Tree를 사용하는지에 대해 알아보자.

일반적으로 트리는 이렇게 생겼다. 인덱스는 정렬이 되어 있기 때문에 분할정복 방식으로 평균 O(logN)의 시간 복잡도로 트리 내에서 데이터를 찾을 수 있다고 한다

그러나 데이터는 언제 추가되고 삭제 될지 모른다.

 

산전수전을 다 겪은 테이블은 이런 형태가 될 수도 있다.

이렇게 한 쪽으로 편향된 트리는 검색을 위해 모든 노드를 순회 해야하므로검색 성능이 O(N)까지 떨어 진다.

그래서 데이터베이스에서는 B Tree를 사용한다고 합니다.

B는 Balanced의 약자로 언제나 같은 높이의 트리를 유지하기 때문에 검색 성능을 유지 시킬 수 있다.

이러니 B Tree를 사용하는 것 같다.

 

B-Tree는 아래와 같이 생겼다.

값을 찾기 위해서 일반적인 트리처럼 좌, 우측만을 사용하지 않고 노드에 저장된 값 사이의 포인터를 통해 탐색한다.

위 그래프에서 14라는 값을 찾는다고 하면, 14는 7,15 사이에 있으므로 가운데 연결된 (9, 11) 노드로 내려가고 14는 11보다 크므로 11의 오른쪽 노드로 내려가서 14라는 값에 도달하게 된다.

실제로는 한 노드에 많은 값들이 정렬된 상태로 존재한다.

노드가 추가 되거나 삭제 될 때는 한 노드에 얼마나 많은 값들이 존재할 수 있는지 체크를 하고 값을 맨 아래 리프노드의 적절한 위치에 넣은 후 제 자리를 찾아가게 된다.

예를 들면 13이라는 값이 추가 되면 최초에는 (12,14) 노드 사이에 들어간다. 하지만 한 노드에 2개 값만 존재할 수 있으므로(위 트리의 경우에만) 13이 한 단계 한 단계 레벨을 올리며 자기 자신의 자리를 찾아가게 된다.

이 과정을 페이징이라고 한다.

B+Tree

B-Tree는 데이터의 검색에는 유리하다. 하지만 모든 데이터를 풀 스캔하려면 모든 트리를 전부 방문해야 한다.

이러한 단점을 개선한 것이 B+Tree이다.

대부분의 관계형 데이터베이스 시스템(RDBMS)에서 기본으로 사용하는 인덱스 구조입니다.

B+Tree는 리프 노드에만 데이터를 저장하고 모든 리프노드를 Linke List를 통해 연결한다.

이렇게 하면 리프노드를 제외한 루트, 브랜치 노드에는 데이터를 저장하지 않기 때문에 메모리가 남고 그 남는 메모리를 중간 브랜치 노드에 키 값을 저장하는데 사용할 수 있다.

즉 트리의 높이가 낮아지므로 검색 속도가 빨라진다.

또 테이블 풀스캔을 하는 경우에도 리프 노드에 어차피 모든 데이터가 있고 모두 Linked List로 연결되어 있으므로 풀 스캔시에도 B-Tree 보다 유리하다.범위 스캔을 하는 경우에도 LinkedList를 통해 효울적인 순차 검색을 할 수 있다.

하지만 B+Tree는 모든 데이터가 리프노드에 있기 때문에 값을 찾기 위해서 어떻게든 리프노드에 도달해야만 하고 브랜치 노드에서 키를 올바르게 찾아가기 위해 중복된 키가 존재할 수도 있다.

 

관계형 데이터베이스에서 B+트리 인덱스를 사용하는 예:

• MySQL: MySQL의 대표적인 저장 엔진인 InnoDB는 B+트리 인덱스를 사용하여 데이터를 관리합니다.
• PostgreSQL: PostgreSQL도 B+트리 인덱스를 기본 인덱스 구조로 사용합니다.
• Oracle: Oracle 데이터베이스 역시 B+트리 기반 인덱스를 사용하여 데이터 조회 속도를 높입니다.

 

 

 

 

참조

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