인덱스(2) : 인덱스가 데이터를 검색하는 방법

목차

 

이전 게시물 

https://lotuus.tistory.com/166

인덱스(1) : 사용하는 이유, 정의, 데이터

 

 

 

앞에서 인덱스가 없는 경우, Full Table Scan 방식을 이용하여 검색하는 것을 알아봤습니다.

그렇다면 인덱스가 있는 경우엔, 어떤 방식을 사용하길래 데이터를 빠르고 효과적으로 검색할 수 있는 것일까요?

인덱스를 구현하는 방식은 대표적으로 3가지가 있으며,

인덱스를 생성할 때 구현 방식을 설정할 수 있습니다.

• HashTable
• B-Tree (B+Tree)
• Full-Text Search

각각의 구현방식, 장점, 단점을 알아보겠습니다.

 

 

Hash Table

https://en.wikipedia.org/wiki/Hash_table

구현방법

• 컬럼의 값을 해시값으로 변환합니다.
• 해시값을 인덱스로 사용하여 데이터를 맵핑합니다.
• 해시값이 충돌하는 경우, 두가지 방법 중 선택합니다.
  • 개방주소법 : 빈 인덱스를 탐색하여 데이터를 저장합니다.
  • 체이닝 : 해당 인덱스에 LinkedList를 사용하여 데이터를 연결하여 저장합니다.

 

장점

• 등호(=) 연산자를 사용하는 일치 검색에 매우 효율적입니다.
  • 해시는 같은 입력에 대해 같은 해시값을 반환하기 때문
• 해시의 길이는 고정되어 있어서, 컬럼의 값이 길어도 공간 사용이 효율적입니다.

 

단점

• 부등호(<, >)를 사용하는 범위 검색이나 정렬에 적합하지 않습니다.
  • 해시값은 랜덤하게 분포되기 때문에, 데이터가 정렬되지 않습니다.
• 범위검색과 정렬을 하려면, 모든 데이터에 접근해야합니다.

 

 

 

 

B-Tree

예시 : 25에서 35까지 데이터 가져오기

• 탐색횟수 : 3회
• 데이터 접근 횟수 : 7회

 

구현방법

• 이진 탐색 트리를 일반화한 형태입니다.
• 왼쪽 노드는 나보다 작은 컬럼 값, 오른쪽 노드는 나보다 큰 컬럼 값으로 구성합니다.
• 균형을 맞추어 노드를 분할합니다.
  • 노드가 한쪽으로 쏠리는 경우, 선형구조와 비슷해져 탐색 효율이 저하됩니다.
• 노드는 Key(컬럼의 값)와 Pointer(레코드 위치값)를 가지도록 구성합니다.
• 각 노드는 N개의 자식노드를 가질 수 있도록 합니다.
• N개의 자식노드는 정렬하여 저장합니다.

 

장점

• 해시 테이블에 비해 탐색하는 범위가 적습니다.
• 데이터가 이미 정렬되어 있기 때문에, 범위검색과 정렬에 효과적입니다.
• 탐색하며 중간 중간 필요한 데이터를 가져올 수 있습니다.

 

단점

• 데이터를 가져오는 과정이 비효율적일 수 있습니다. (데이터 접근 횟수 참고)

 

 

 

B+Tree

예시 : 25에서 35까지 데이터 가져오기

• 탐색횟수 : 3회
• 데이터 접근 횟수 : 6회 (B-Tree에 비해 1회 감소)

 

구현방법

• B-Tree를 개선한 구조입니다.
• 현재 가장 보편적으로 사용되는 인덱스 구현 방식입니다.
• 리프 노드만 Key(컬럼의 값)와 Pointer(레코드 위치값)를 가지도록 구성합니다.
• 다른 노드는 Key만 가지도록 구성합니다.
• Pointer을 찾기 위해선 리프 노드로 가야하기 때문에, 노드 간 중복 Key가 존재할 수 있습니다.
• 리프 노드끼리는 LinkedList 형태로 연결합니다.

 

장점

• 리프 노드가 연결되어있기 때문에 B-Tree보다 더 효율적으로 범위검색과 정렬이 가능합니다.

 

단점

• B-Tree와 다르게, 실제 데이터에 접근하기 위해선 반드시 리프 노드까지 탐색해야합니다.

 

 

 

 

Full-Text Search

구현방법

• char, varchar, text 타입 데이터를 빠르게 검색해줍니다.
• 문자열을 Tokenizing한 인덱스 데이터를 저장합니다.
• Tokenizing 방법
  • Built In Parser 방식 : 공백, 특정 단어를 기준으로 단어를 분리합니다.
  • N-gram Parser 방식 : N개 크기로 단어를 분리합니다. (mysql 기준 default 2개)

예시문장
안녕하세요. 오늘 날씨가 참 좋네요.

built-in 방식
안녕하세요, 오늘, 날씨가, 참, 좋네요

n-gram 방식
안녕, 녕하, 하세, 세요, 요오, 오늘, 늘날, 날씨, 씨가, 가참, 참좋, 좋네, 네요

 

 

장점

• 첫 글자, 중간 단어, 문장으로도 인덱스를 생성해주기 때문에 문자 검색에 효율적이다.

 

단점

• 문자를 인덱싱하므로 더 많은 저장공간이 필요합니다.

 

정리

• 문자를 검색해야할 경우 사용하면 효과적입니다.

 

 

 

다음 게시물

https://lotuus.tistory.com/168

인덱스(3) : 인덱스 종류