10.3.9 Comparison of B-Tree and Hash Indexes

10.3.9 B-Tree와 Hash Index 비교

B-tree와 hash 데이터 구조를 이해하면, 이러한 데이터 구조를 인덱스에 사용하는 서로 다른 스토리지 엔진에서 서로 다른 쿼리가 어떻게 수행되는지 예측하는 데 도움이 됩니다. 특히 B-tree 또는 hash 인덱스 중에서 선택할 수 있는 MEMORY 스토리지 엔진의 경우에 그렇습니다.

• B-Tree Index Characteristics

• Hash Index Characteristics

B-Tree Index Characteristics

B-tree 인덱스는 =, >, >=, <, <=, 또는 BETWEEN 연산자를 사용하는 식에서 컬럼 비교에 사용할 수 있습니다. 또한 인덱스는 인수가 와일드카드 문자로 시작하지 않는 상수 문자열인 경우 LIKE 비교에도 사용할 수 있습니다. 예를 들어, 다음 SELECT 문은 인덱스를 사용합니다:

SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%'; SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

첫 번째 문에서는 'Patrick' <= key_col < 'Patricl'인 row만 고려됩니다. 두 번째 문에서는 'Pat' <= key_col < 'Pau'인 row만 고려됩니다.

다음 SELECT 문은 인덱스를 사용하지 않습니다:

SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%'; SELECT * FROM tbl_name WHERE key_col LIKE other_col;

첫 번째 문에서는 LIKE 값이 와일드카드 문자로 시작합니다. 두 번째 문에서는 LIKE 값이 상수가 아닙니다.

... LIKE '%string%'을 사용하고 _string_이 세 글자보다 길면, MySQL은 Turbo Boyer-Moore 알고리즘을 사용하여 문자열에 대한 패턴을 초기화한 다음 이 패턴을 사용해 검색을 더 빠르게 수행합니다.

col_name IS NULL을 사용하는 검색은 _col_name_에 인덱스가 있으면 인덱스를 사용합니다.

WHERE 절의 모든 AND 레벨을 span하지 않는 어떠한 인덱스도 쿼리를 최적화하는 데 사용되지 않습니다. 즉, 인덱스를 사용하려면, 인덱스의 프리픽스가 모든 AND 그룹에서 사용되어야 합니다.

다음 WHERE 절은 인덱스를 사용합니다:

... WHERE index_part1=1 AND index_part2=2 AND other_column=3

/* index = 1 OR index = 2 */

... WHERE index=1 OR A=10 AND index=2

/* optimized like "index_part1='hello'" */

... WHERE index_part1='hello' AND index_part3=5

/* Can use index on index1 but not on index2 or index3 */

... WHERE index1=1 AND index2=2 OR index1=3 AND index3=3;

다음 WHERE 절은 인덱스를 사용하지 않습니다:

/* index_part1 is not used */

... WHERE index_part2=1 AND index_part3=2

/*  Index is not used in both parts of the WHERE clause  */

... WHERE index=1 OR A=10

/* No index spans all rows  */

... WHERE index_part1=1 OR index_part2=10

때때로 MySQL은 인덱스가 사용 가능하더라도 이를 사용하지 않습니다. 이러한 상황 중 하나는 옵티마이저가 인덱스를 사용하면 테이블의 매우 큰 비율의 row에 접근해야 할 것이라고 추정하는 경우입니다. (이 경우에는 seek 횟수가 더 적기 때문에 테이블 스캔이 훨씬 더 빠를 가능성이 큽니다.) 그러나 이러한 쿼리가 LIMIT를 사용하여 일부 row만 검색하는 경우, MySQL은 반환할 소수의 row를 훨씬 더 빠르게 찾을 수 있으므로 어쨌든 인덱스를 사용합니다.

Hash Index Characteristics

Hash 인덱스는 앞에서 설명한 것과는 다소 다른 특징을 갖습니다:

• = 또는 <=> 연산자를 사용하는 equality 비교에만 사용됩니다 (하지만 매우 빠릅니다). 값의 범위를 찾는 < 같은 비교 연산자에는 사용되지 않습니다. 이러한 단일 값 조회에 의존하는 시스템은 “key-value store”로 알려져 있습니다. 이와 같은 애플리케이션에 MySQL을 사용하려면 가능한 곳에서는 hash 인덱스를 사용하십시오.

• 옵티마이저는 ORDER BY 연산을 가속화하기 위해 hash 인덱스를 사용할 수 없습니다. (이 유형의 인덱스는 다음 엔트리를 순서대로 검색하는 데 사용할 수 없습니다.)

• MySQL은 두 값 사이에 대략 몇 개의 row가 있는지 결정할 수 없습니다 (이는 range 옵티마이저가 사용할 인덱스를 결정하는 데 사용됩니다). 이는 MyISAM 또는 InnoDB 테이블을 hash 인덱스가 있는 MEMORY 테이블로 변경하는 경우 일부 쿼리에 영향을 줄 수 있습니다.

• 전체 key만이 row를 검색하는 데 사용될 수 있습니다. (B-tree 인덱스의 경우, key의 어떤 leftmost 프리픽스든 row를 찾는 데 사용할 수 있습니다.)