5.3 B-Tree 인덱스 & 5.4 해시 인덱스

July 29th, 2021

B-Tree는 데이터베이스의 인덱싱 알고리즘 중에서도 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. 거기에 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다.
B-Tree 알고리즘에는 여러가지 변형된 형태가 있는데, B+-Tree 또는 B*-Tree가 사용된다.
B-Tree는 컬럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지하고 있다. 전문 검색과 같은 특수한 조건이 아닐 경우, 대부분 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다.

5.3.1 구조 및 특성

B-Tree는 트리 구조의 최상위에 하나의 루트 노드가 존재하고, 그 하위에 자식 노드가 붙어있는 형태이다.
트리 구조의 가장 하위에 있는 노드를 리프 노드라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 브랜치 노드라고 한다.
DB에서 인덱스와 실제 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있다.

인덱스의 키 값은 모두 정렬되어 있지만 데이터 파일의 레코드는 임의의 순서대로 저장되어 있다.
인덱스는 테이블의 키 컬럼만 가지고 있기 때문에, 다른 정보를 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다.
인덱스의 리프노드에는 항상 해당 레코드의 레코드 주소를 가르키는데 이 레코드 주소는 DBMS 종류나 MySQL 스토리지 엔진에 따라 의미가 달라진다.
- 오라클 DBMS : 물리적인 레코드 주소
- MyISAM : 내부적인 레코드의 아이디(번호)
- InnoDB : 프라이머리 키 값

5.3.2 B-Tree 인덱스 키 추가 및 삭제

테이블의 레코드를 저장사거나, 변경하는 경우, 인덱스 키 추가나 삭제 작업이 발생한다. 이 때 인덱스 키 추가나 삭제가 어떻게 발생하느냐를 이해하면 쿼리의 성능을 쉽게 예측할 수 있기 때문에 이에 관련된 내용을 알아보자.

인덱스 키 추가

새로운 키 값이 B-Tree에 저장될 때, 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고, 그렇지 않을 수도 있다.
B-Tree에 저장도리 때는 저장될 키 값을 이용해 B-Tree상 적절한 위치를 검색해야 한다. 만일 리프 노드가 꽉 차서 저장할 수 없을 때는 리프노드가 분리되어야 하는데, 이 때는 상위 브랜치 노드까지 작업해야 할 수 있다.
일반적으로 테이블에 레코드를 추가하는 작업 비용을 1이라고 하면, 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1~1.5로 예측하는 것이 일반적이다.
MyISAM이나 Memory 스토리지 엔진을 사용하는 테이블에서는, INSERT문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스에 반영한다. => 키 추가 작업을 완료하기 전까지 클라이언트는 대기 상태

인덱스 키 삭제

B-Tree의 키 값이 삭제되는 경우는 추가하는 경우보다 간단하다. 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아 삭제 마크만 하면 작업이 완료된다.
InnoDB 스토리지 엔진(5.5 이상)은 작업이 버퍼링되어 지연처리 할 수 있지만, MyISAM or Memory 스토리지 엔진은 인서트 버퍼와 같은 기능이 없어 클라이언트가 대기를 해야 한다.

인덱스 키 변경

인덱스의 키 값에 따라 저장될 리프 노드의 위치가 결정되기 때문에, 단순히 인덱스의 키 값만 변경하는 것은 불가능하다.
그렇기 때문에 인덱스 키 값 변경은 키 값 삭제 -> 키 값 추가의 순서대로 진행된다.

인덱스 키 검색

INSERT, UPDATE, DELETE의 비용을 감수하면서 인덱스를 사용하기 위한 목적은 빠른 조회이다.
인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 트리 탐색이 불가능 하다는 점을 유의하자!!

5.3.3 B-Tree 인덱스 사용에 영향을 미치는 요소

B-Tree 인덱스는 인덱스를 구성하는 컬럼의 크기와 레코드 건수, 그리고 유니크한 인덱스 키 값의 개수에 의해 검색/변경 작업의 성능에 영향을 받는다.

인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라고 하며, 디스크의 모든 읽기/쓰기의 최소 작업 단위가 된다.
MySQL의 B-Tree는 자식 노드의 개수가 가변적이며, 인덱스의 페이지 크기와 키 값의 크기에 따라 개수가 결정된다.
InnoDB의 모든 페이지 크기는 16KB로 고정되어 있다.
만약 인덱스의 키가 16바이트라고 가정하고, 자식노드 주소가 12바이트라고 한다면 하나의 인덱스 페이지는 16 * 1024 / (16+12) = 585개의 키를 저장할 수 있다.

B-Tree 깊이

B-Tree의 깊이는 상당히 중요하지만 직접적으로 제어할 방법이 없다.
인덱스 키 값이 커질수록 하나의 인덱스 페이지가 담을 수 있는 키 값의 개수가 작아지고, 그로인해 B-Tree의 깊이가 깊어져 더 많은 디스크 읽기가 필요해진다.
인덱스 키값의 크기는 가능하면 작게 만드는것이 좋다.

선택도(기수성)

인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)은 거의 같은 의미로 사용되며, 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다. (전체 인덱스의 키 값은 100개인데, 유니크한 값의 수가 10개라면 기수성은 10이다)
인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지고 선택도 또한 떨어진다.
인덱스는 선택도가 높을수록 대상이 줄어들기 때문에 그만큼 빠르게 처리된다. 그렇기 때문에 인덱스는 최대한 카디널리티가 놓은 것을 선택하자.

읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은, 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는것 보다 높은 비용이 드는 작업이다.(일반적인 옵티마이저에서는 인덱스를 통해 1건 읽는게 직접 레코드에서 1건 읽는것 보다 4~5배 정도 비용이 더 많이 든다.)
인덱스를 통해 읽어야 할 레코드 건수가 20~25%가 넘어가면 인덱스를 이용하지 않고 직접 테이블을 읽는게 효율적이다.

5.3.4 B-Tree 인덱스를 통한 데이터 읽기

어떤 경우 인덱스 사용을 유도할지, 또는 사용하지 못하게 할지 판단하려면 MySQL이 어떻게 인덱스를 이용해서 레코드를 읽는지 알아야 한다. 여기서는 MySQL이 인덱스를 이용하는 대표적인 방법 3가지를 알아볼 것이다.

인덱스 레인지 스캔

인덱스의 접근방법 중 가장 대표적인 접근방식으로, 제일 빠른 방법이다.
인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 검색하려는 값의 수나, 검색 결과 레코드 건수와 관계 없이 레인지 스캔이라고 표현한다.
인덱스 리프노드까지 가서 검색해야 할 레코드의 인덱스를 찾고 나서, 레코드 주소를 기반으로 실제 레코드를 찾는 과정ㅇ이 필요하다. 이 때, 레코드 한 건 한 건 단위로 랜덤 I/O가 발생한다.
그래서 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블 풀 스캔이 더 효율적이다.

인덱스 풀 스캔

인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만, 인덱스의 처음부터 끝까지 모두 읽는 방식이다.
대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫번째 컬럼이 아닌 경우 인데그 풀 스캔 방식이 사용된다. ( 인덱스는 컬럼 A,B,C순으로 만들어졌는데 B나 C컬럼으로 검색할 경우)
보통은 인덱스에 명시된 컬럼만으로 SELECT 처리를 완료할 때 사용한다.

루스 인덱스 스캔

오라클의 인덱스 스킵 스캔이라는 기능과 동작 방식이 비슷하다.
루스 인덱스 스캔은 말그대로 느슨하게 또는 듬성듬성 인덱스를 읽는 것을 말한다.
루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 동작하지만, 중간중간마다 필요치 않은 인덱스 키값은 무시(SKIP)하고 다음으로 넘어간다.
일반적으로 GROUP BY 또는 집합 함수 가운데 MAX(), MIN() 함수에 대해 최적화를 하는 경우 사용된다.

SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dept_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;

dept_emp 테이블은 (dept_no, emp_no) 기준으로 인덱스가 생성되어 있다. 이 인덱스는 dept_mp + emp_no 기준으로 정렬이 되어 있어 dept_no기준으로 첫번째 emp_no의 값만 읽어오면 된다. 이렇게 루스 인덱스 스캔을 사용할 수 있다.

5.3.5 다중 컬럼(Multi-column) 인덱스

두 개 이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스라고 하며, Concatenated Index라고도 부른다.
인덱스의 두번째 컬럼은 첫번째 컬럼에 의존해 정렬되어 있다. 즉, 두 번째 컬럼의 정렬은 첫 번째 컬럼이 똑같은 레코드에서만 의미가 있다.

5.3.6 B-Tree 인덱스의 정렬 및 스캔 방향

인덱스 키 값은 항상 오름차순으로 정렬되지만, 인덱스를 거꾸로 읽으면 내림차순으로 정렬된 인덱스로 사용할 수 있다.
인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 결정한다.

인덱스의 정렬

일반적인 DBMS는 인덱스를 생성하는 시점에 인덱스를 구성하는 컬럼의 정렬을 오름차순으로 할 지 내림차순으로 할 지 결정할 수 있다.
하지만 MySQL은 정렬방식을 혼합해서 생성하는 기능을 지원하지 않는다.

` CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC); `

위와 같이 인덱스를 생성해도, ASC/DESC을 무시하고 모든 컬럼이 오름차순으로만 정렬된다.

인덱스 스캔 방향

인덱스는 항상 오름차순으로 정렬되어 있지만 인덱스를 최소값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최대값부터 거꾸로 읽으면 내림차순으로 가져올 수 있다.
그래서 인덱스를 역순으로 정렬되게 할 수는 없지만, 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다.

5.3.7 B-Tree 인덱스의 가용성과 효율성

쿼리의 WHERE 조건이나 GROUP BY 또는 ORDER BY 절이 어떤 경우 인덱스를 사용할 수 있고, 어떤 방식으로 사용할 수 있을지 식별할 수 있어야 한다. 그래야 쿼리의 조건을 최적화 하거나, 역으로 쿼리에 맞게 인덱스를 최적의 방식으로 생성할 수 ㅣㅇㅆ기 때문이다.
이 챕터에서는 어떤 조건에서 인덱스를 생성할 수 있는지의 여부와, 인덱스를 100% 활용하는지, 일부만 이용하게 되는지에 대해서 알아본다.

비교 조건의 종류와 효율성

다중 컬럼 인덱스에서는 각 컬럼의 순서와 컬럼에 사용된 조건(동등비교 or 범위 비교)에 따라 인덱스 컬럼의 활용 형태가 달라지며, 효율도 다르다.

SELECT * from dept_emp
WHERE dept_no = 'd002' AND emp_no >= 10114;

만일 위 쿼리에 순서만 다른 인덱스 2개를 생성했다고 가정해보자, 각각의 인덱스는 어떻게 처리를 할까 ?
- 케이스 A : dept_no + emp_no
- 케이스 B : emp_no + dept_no
케이스 A는 dept_no = ‘d002’ AND emp_no >= 10114인걸 찾고, dept_no가 ‘d002’가 아닐때까지 인덱스를 순차적으로 읽는다. 5건의 레코드를 찾는데 5번의 비교 작업만 수행한다고 볼 수 있다.
케이스 B는 우선 emp_no >= 10144인 레코드를 찾고, 그 이후 모든 레코드에 대해 dept_no=’d002’인지를 검증하는 작업을 한다.
dept_no와 emp_no처럼 작업의 범위를 결정하는 조건을 작업 범위 결정 조건이라고 한다.
dept_no=’d002’처럼 비교 작업의 범위를 좁히지 못하고 거름종이 역할을 하는 조건을 필터링 조건 또는 체크 조건이라고 표현한다.
emp_no >=10144는 비교 작업의 범위를 좁혀주기 때문에 실질적인 작업 범위 결정 조건이라고 할 수 있다.
작업 범위를 결정하는 조건은 많으면 많을수록 쿼리의 처리 성능을 높이지만, 체크 조건은 많다고 해서 쿼리의 처리 성능을 높이지는 못한다.

인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른 쪽 값이 정렬되어 있다는 것이다. (단일컬럼, 다중컬럼 다 동일하다) 동일하게 두가지 케이스가 있을때의 상황에 대해 알아보자 : *.케이스 A : first_name * 케이스 B : dept_no, emp_no

SELECT * FROM employees WHERE first_name LIKE '%mer';

*케이스 A에서 위와 같은 방식으로 쿼리를 조회하면 인덱스 레인지 방식을 사용할 수 없다. 왼쪽 부분이 고정되어 있지 않기 때문이다.

SELECT * FROm dept_emp WHERE emp_no >= 10144;

케이스 B에서 위와 같은 방식으로 쿼리 조회시에도 인덱스를 효율적으로 사용할 수 없다.인덱스는 dept_no에 대해 먼저 정렬한 후, emp_no 컬럼으로 정렬하기 때문이다.

가용성과 효율성 판단

기본적으로 B-Tree인덱스의 특성상 아래 조건에서는 작업 범위 결정 조건으로 사용할 수 없다.

NOT-EQAUL로 비교된 경우( “<>”,”NOT IN”, “NOT BETWEEN”, “IS NOT NULL”)
LIKE ‘%??’
스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형된 후 비교된 경우
NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
데이터 타입이 서로 다른 비교
문자열 데이터 타입의 콜레이션이 다른 경우

INDEX ix(text( column_1, column_2, column_3, ..., column_n)

작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우
- column_1에 대한 조건이 없는 경우
- column_1 컬럼이ㅡ 비교 조건이 위의 인덱스 사용 불가 조건 중 하나 일 경우
작업 범위 결정 조건으로 인덱스를 사용하는 경우
- column_1~column(i-1) 까지는 Equal (=, IN)으로 비교
- column_i 컬럼에 대해 아래중 하나 연산자로 비교
  - Equal(=, IN)
  - 크거나 작은 형태(>, <)
  - LIKE로 좌측 일치 패턴

5.4 Hash 인덱스

해시 인덱스는 동등 비교 검색에는 최적화 되어 있지만, 범위검색 혹은 정렬된 결과를 가져오는 데에는 사용하기 적합하지 않다.
해시 인덱스는 일반적으로 메모리 기반 테이블에 주로 구현되어 있으며, 디스크 기반의 데용량 테이블용으로는 거의 사용되지 않는다.

5.4.1 구조 및 특성

해시. 인덱스의 가장 큰 장점은 실제 키 값과는 관계없이 인덱스 크기가 작고 검색이 빠르다는 것이다.
해시 인덱스는 트리 형태가 구조의 아니기 떄문에, 검색하는 갓을 주면 해시함수를 거쳐 찾고자 하는 키값이 포함된 버킷을 찾을 수 있다.
해시 인덱스는 원래 키값을 저장하는 것이 아니라 해시 함수의 결과를 저장하기 때문에 키 값이 아무리 커도 4~8바이트 수준의 데이터만 저장이 되어 B-Tree 인덱스 대비 크기가 작다.
해시 인덱스에서 가장 중요한 것은 해시 함수이다. 해시 함수의 결과 값 범위가 넓으면 그만큼 많은 버킷이 필요해 공간의 낭비를 야기하고, 결과 값의 범위가 작으면 충돌되는 케이스가 많이 발생해 인덱스의 장점이 사라진다.
해시 인덱스를 지원하는 MEMORY 스토리지 엔진, NDB 클러스터의 경우 이미 해시 함수를 내장하고 모든 처리를 자동으로 해주기 때문에 사용자가 해시 함수를 개발할 일은 없다.
하지만 해시 인덱스를 지원하지 않는 InnoDB 스토리지 엔진에서는 인위적으로 해시 함수를 이용해 해시 인덱슻처럼 작동하토록 테이블을 만들 수 있다.

5.4.2 해시 인덱스의 가용성 및 효율성

해시 인덱스는 빠른 검색을 제공하지만 키 값 자체가 변환되어 저장되기 때문에, 범위를 검색하거나 원본 값 기준으로 정렬 할 수 없다.

아래 예시를 통해 해시 인덱스를 사용할 수 있는 쿼리와, 사용하지 못하는 쿼리를 확인해보자.

SELECT * FROM tb_hash WHERE column = '검색';
SELECT * FROM tb_hash WHERE column <=> '검색';
SELECT * FROM tb_hash WHERE column IN ( '검색1', '검색2');
SELECT * FROM tb_hash WHERE column IS NULL;
SELECT * FROM tb_hash WHERE column IS NOT NULL;

위 쿼리는 동등 비교 조건으로 값을 검색하고 있어 해시 인덱스의 빠른 장점을 그대로 이용할 수 있다.
<=> 는 Null-Safe Equal연산자라고 하는데, 비교 양쪽의 값이 NULL이 있을 때를 제외하고는 ‘=’와 동일하다.

SELECT * FROM tb_hash WHERE column >= '검색';
SELECT * FROM tb_hash WHERE column BETWEEN 100 AND 200';
SELECT * FROM tb_hash WHERE column LIKE '검색%';
SELECT * FROM tb_hash WHERE column <> '검색';

대체적으로 위와 같이 범위 비교나 부정형 비교는 해시 인덱스를 사용할 수 없다.

CREATE TABLE tb_session (
	session_id BITINT NOT NULL,
	member_id CHAR(20) NOT NULL,
	....
	INDEX ix_memberid_sessionid (member_id, session_id) using HASH
) ENGINE=MEMORY;
SELECT * FROM tb_session WHERE member_id = 'user_nickname';

위 케이스에서는 member_id, session_id 두 개의 컬럼으로 해시 인덱스를 만들었다. 이 때 하나의 컬럼(첫번째 컬럼이더라도)만 동등조건으로 비교된다고 하더라도 ix_memberid_sessionid 인덱스를 사용할 수 없다.

참고자료 : Real MySQL - 5.3 B-Tree 인덱스, 5.4 해시 인덱스

database (19)

oksusutea's blog

꾸준히 기록하려고 만든 블로그