데이터베이스의 인덱스 알고리즘

데이터베이스 인덱스 알고리즘은 대표적으로 B-tree, Hash로 구분할 수 있고, Fractal-Tree 알고리즘도 존재합니다.

B-Tree 알고리즘

• 가장 일반적으로 사용되는 인덱스 알고리즘
• 칼럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘
• 범위 탐색이 가능하다
• like와 같은 구문을 실행할 때도 사용할 수 있다

Hash 알고리즘

• 컬럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘
• 매우 빠른 검색을 지원합니다
• 값을 변형해서 인덱싱하기 때문에 값의 일부만 검색할 때는 사용할 수 없습니다.
• 주로 메모리 기반 데이터베이스에서 많이 사용합니다

Fractal-Tree 알고리즘

• B-Tree의 단점을 보완하기 위해 고안된 알고리즘으로 독점적인 특허로 등록되어 MySQL의 스토리지 엔진인 TokuDB에 적용되어 있다.
• B-Tree 인덱스에서 인덱스 키를 검색하거나 변경하는 과정 중에 발생하는 가장 큰 문제는 디스크의 랜덤 I/O가 상대적으로 많이 필요하다는 것인데 Fractal-Tree에서는 이러한 점을 최소화하고, 이를 순차 I/O로 변환해서 처리할 수 있다.
• 즉, 값을 변형하지 않고 인덱싱하며 범용적인 목적으로 사용할 수 있는 측면에서 B-Tree와 거의 유사하지만 데이터가 저장되거나 삭제될 때 처리 비용을 상당히 줄일 수 있게 설계된 것이 특징이다.
• 인덱스 키가 추가되거나 삭제될 때 B-Tree인덱스보다 더 많은 정렬 작업이 필요하며, 이 때문에 더 많은 CPU처리가 필요할지 모르지만 인덱스의 단편화가 발생하지 않도록 구성할 수 있고, 인덱스의 키값을 클러스터링 하기 때문에 B-Tree보다는 대용량 테이블에서 높은 성능을 보장한다.
• 평균적인 처리 능력이 이론적으로 B-Tree보다 400배 가량 빠르며, 실제로 TokuDB의 키 추가 및 삭제작업은 InnoDB보다 100배 가량 빠른 처리 속도를 보여준다.
• 하지만 InnoDB보다 동시성처리가 불안정하다는 단점이 있다.