REAL MYSQL 8장 인덱스 (8~8.3)

[somefood]

인덱스

• 데이터베이스 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건
• 순차 I/O, 랜덤 I/O 중 순차 I/O가 성능이 더 잘나온다. 하지만 랜덤 I/O로 조회되는 경우가 더 많기에 MySQL에선 그룹 커밋이나 바이너리 로그 버퍼 또는 InnoDB 로그 버퍼 등의 기능을 활용한다.
• 어찌됐건 쿼리를 튜닝한다는 것은 랜덤 I/O 자체를 줄여주는 작업이라 보면 된다.
• 인덱스 레인지 스캔은 랜덤 I/O를 풀 테이블 스캔은 순차 I/O를 사용

인덱스란

• 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍(key - value pair)으로 구성
• 정렬이 항상 되어 있어야 한다.
• SELECT 쿼리 문장의 WHERE 조건절에 사용되는 칼럼이라고 해서 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져 오히려 역효과가 날 수 있다.
• 인덱스(키)의 종류는 다음과 같이 분류할 수 있음
  • 프라이머리 키: 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스. 테이블에서 해당 레코드를 식별할 수 있는 기준값이 되기 때문에 식별자라고도 부름 NULL 값을 허용하지 않으며 중복을 허용하지 않음
  • 세컨더리 인덱스: 프라이머리 키 제외한 나머지. 유니크 인덱스는 프라이머리 키와 성격이 비슷하고 프라이머리 키를 대체해서 사용할 수 있어 대체키라고도 부름
• 데이터 저장 방식(알고리즘) 별로 구분
  • B-Tree 인덱스: 가장 일반적으로 사용. 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱함
  • Hash 인덱스: 해시값을 계산해서 인덱싱하는 알고리즘. 매우 빠른 검색 지원. 값은 변경해서 인덱싱하므로 전방(Prefix) 일치와 같이 값의 일부만 검색하거나 범위를 검색할 때는 이 인덱스를 사용할 수 없음. 메모리 기반의 데이터베이스에서 많이 사용 (Redis)

B-Tree 인덱스

B-Tree 설명 참고

• 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘. 여전히 가장 범용적으로 사용된다.
• Binary(이진)의 B가 아니라 Balanced의 B이다.
• 칼럼의 원래 값을 변형시키지 않음 (앞부분을 잘라 관리하긴 함)
• 인덱스 구조체 내에서 항상 정렬된 상태를 유지
• 구조는 다음과 같음
  • 루트 노드(Root node): 최상위에 하나가 존재하고 아래에 자식 노드가 붙어 있음
  • 브랜치 노드(Branch node): 중간에 위치한 브랜치
  • 리프 노드(Leaf node): 가장 하위에 위치한 노드
• 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되며, 인덱스의 리프노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있음
• InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다.
  • 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다.
  • InnoDB는 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한 번 검색한다.

인덱스 키 추가

• 새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 않을 수도 있다.
• B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절할 위치를 검색
• 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프노드에 저장한다.
• 리프노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하며, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 이런 작업으로 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 드는 것으로 알려짐

인덱스 키 삭제

• 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업 완료
• 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있음.
• 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하여 디스크 I/O가 필요함
• MySQL 5.5이상 버전에선 버퍼링되어 지연 처리될 수 있음
• 처리가 지연된 인덱스 키 삭제 또한 사용자에게 특별한 악영향 없이 내부적으로 처리하므로 걱정할 필요 없다.

인덱스 키 변경

• 인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스상의 키 값만 변경하는 것은 불가능함
• B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.
• 즉, 삭제와 추가 작업이 절차대로 진행

인덱스 키 검색

• INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구착하는 이유는 바로 빠른 검색 때문
• 인덱스를 검색하는 작업은 루트 노드부터 브랜치, 리프 노드까지 이동하면서 비교작업을 수행하며 이를 트리 탐색이라고 함
• SELECT 뿐만 아니라 UPDATE, DELETE 처리할 때도 사용됨
• B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있음
• 부등호 (<, >) 비교 조건에서도 활용할 순 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 사용할 수 없음.
• 또한 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에도 B-Tree의 인덱스를 절대 탈 수 없음 -> 이미 변형된 값은 B-Tree 인덱스에 존재하는 것이 아니기 때문
  • 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업에서 사용 어려우니 이 점 주의
• InnoDB 스토리지 엔진에서 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있음
• UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다. 심지어 테이블의 모든 레코드를 잠글 수 있다.

인덱스 설계가 많이 중요하고 많은 부분에 영향을 미침!!

인덱스 키 값의 크기

• InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) or 블록(Block)이라고 함
• B-Tree는 자식 노드의 개수가 가변적인 구조
• 몇 개의 자식 노드를 가질 수 있는지는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정. 기본값은 16KB
• 인덱스 키 값이 커지면 오히려 한 페이지에 보관할 수 있는 수가 적어져 I/O가 더 많아질 수도 있다.
• B-Tree의 깊이(Depth)는 중요하지만 직접 제어할 방법은 없다.

1 인덱스 페이지(16KB)에 16Byte 인덱스의키 개수 => 16 * 1024(Byte) /(16(Byte) + 12(Byte, 노드 주소)) => 585개
깊이가 3인 경우 최대 2억개(585 * 585 * 585)개 정도 가능
인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋고, 대용량 데이터베이스라도 깊이가 5단계 이상까지 깊어지는 경우는 흔치 않음

선택도(기수성)

• 선택도(Selectivity) or 기수성(Cardinality)은 거의 같은 의미로 사용
• 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미함
• 전체 인덱스 키 값은 100개인데, 그중에서 유니크한 값의 수는 10개라면 기수성은 10을 의미
• 인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지고 동시에 선택도 또한 떨어짐
• 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

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

인덱스 레인지 스캔

• 인덱스의 접근 방법 가운데 가장 대표적인 접근 방식
• 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
• 검색하려는 값의 수나 검색 결과 레코드 건수와 관계없이 레인지 스캔이라고 표현함.
• 루느 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 들어가야 필요한 레코드의 시작 지점을 찾을 수 있음
• 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다.
• 스캔하다 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아 스캔함
• 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝냄
• 레코드 한 건 한 건 단위로 랜덤 I/O가 한 번씩 일어난다.
• 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 됨
  1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. 이 과정을 인덱스 탐색(Index seek)라고 함
  2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽음. 이 과정을 인덱스 스캔(Index scan)이라고 함
  3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어옴

쿼리가 필요한 데이터에 따라 3번 과정 필요없을 수 있음 -> 커버링 인덱스라 하며 성능이 빠름

커버링 인덱스 참고

인덱스 풀 스캔

• 인덱스 레인지 스캔과 달리 인덱스의 처음부터 끝까지 모두 읽는 방식
• 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 사용됨
  • 인덱스 (A, B, C) 순으로 만들어져 있지만 쿼리의 조건절은 B 칼럼이나 C 칼럼으로 검색하는 경우
• 인덱스 레인지 스캔보단 빠르진 않지만 테이블 풀 스캔보다는 효율적 (테이블 크키보다 인덱스 크기가 작기 때문)

쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우만 사용 가능!

인덱스 루스 스캔

• 말 그대로 느슨하게 인덱스를 읽는 스캔 방법
• 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어감
• 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화할 때 사용

CREATE TABLE t2 (
    pk_col1 INT NOT NULL,
    pk_col2 INT NOT NULL,
    c1 CHAR(64) NOT NULL,
    c2 CHAR(64) NOT NULL,
    PRIMARY KEY(pk_col1, pk_col2),
    KEY c1_c2_idx (c1, c2)
) ENGINE=INNODB;


INSERT INTO t2 VALUES (1,1,'a','b'), (1,2,'a','b'),
    (1,3,'a','c'), (1,4,'a','c'),
    (2,1,'a','d'), (3,1,'a','b'),
    (4,1,'d','b'), (4,2,'e','b'),
    (5,3,'f','c'), (5,4,'k','c'),
    (6,1,'y','d'), (6,2,'f','b');
	
	
EXPLAIN 
    SELECT c1, MIN(c2)
    FROM t2
    GROUP BY c1 \G

인덱스 스킵 스캔

• 데이터베이스 서버에서 인덱스의 핵심은 값이 정렬돼 있다는 것이며, 인덱스를 구성하는 칼럼의 순서는 매우 중요함

ALTER TABLE employees ADD INDEX ix_gender_birthdate(gender, birth_date);

SELECT * FROM employees WHERE birth_date >= '1965-02-01';

SELECT * FROM employees WHERE gender='M' AND birth_Date>='1965-02-01';

• 두 번째 쿼리는 인덱스를 탈 수 있기에 효율적이지만, 첫 번째는 인덱스를 타지 않기 때문에 효율적으로 사용 불가
• 하지만 8.0 버전부터는 옵티마이저가 gender 칼럼을 건너뛰어서 birth_date 칼럼만으로 인덱스 검색이 가능한 인덱스 스킵 스캔(Index skip scan) 최적화 기능이 도입됨

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

• 쿼리의 WHERE 조건이나 GROUP BY, ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 함
• 그래야만 쿼리의 조건을 최적화하거나, 역으로 쿼리에 맞게 인덱스를 최적으로 생성할 수 있다.

비교 조건의 종류와 효율성

• 다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등 비교(=)인지 아니면 크다, 작다(>, <) 같은 범위 조건에 따라 활용 형태가 달라짐

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

• 위와 같은 컬럼이 있고 다음과 같이 두 가지의 인덱스가 있다.

케이스 A: INDEX(dept_no, emp_no)
케이스 B: INDEX(emp_no, dept_no)

• 케이스 A는 dept_no가 d002가 아닐 때까지 인덱스를 쭉 읽기만 하면 된다. 그래서 위 쿼리에서는 효율적으로 낼 수 있다.
• 케이스 B는 emp_no>=10144 AND dept_no=d002인 레코드를 찾고 그 이후 모든 레코드에 dept_no가 d002인지 비교하는 과정을 거쳐야해서 덜 효율적이다.
• 이렇듯 칼럼 순서를 잘 지정해야 효율적인 인덱스를 만들 수 있다.

인덱스의 가용성

• B-Tree 인덱스의 특징은 왼쪽 값에 기준해서(Left-most) 오른쪽 값이 정렬돼 있다. INDEX(firstname), INDEX(dept_no, emp_no)
• 하나의 칼람으로 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능하다
• 다중 칼럼 인덱스에서 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없음

--- 이런 칼럼이 있음
INDEX (firstname)

-- 인덱스 레인지 스캔 방식 사용 불가.
-- first_name 칼럼에 저장된 값의 왼쪽부터 한 글자씩 비교해 가면서 일치하는 레코드를 찾아야 하는데, 조건절에 주어진 상숫값 ('%mer') 왼쪽 부분이 고정되지 않음
-- 정렬 우선순위가 낮은 뒷부분의 값만으로는 왼쪽 기준 정렬 기반인 B-tree에서 인덱스 효과를 누릴 수 없음
SELECT * FROM employees WHERE first_name LIKE '%mer';

INDEX (dept_no, emp_no)
SELECT * FROM dept_emp WHERE emp_no >= 10144;

-- 이 경우에도 dept_no 조건이 없기 때문에 사용할 수 없다.

가용성과 효율성 판단

아래와 같은 조건에서는 B-Tree 인덱스를 사용할 수 없음

• NOT-EQUAL로 비교된 경우 <>, NOT IN, NOT BETWEEN, IS NOT NULL

WHERE column <> 'N'
WHERE column NOT IN (10, 11, 12)
WHERE column IS NOT NULL

• LIKE '%??'(앞부분 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우

WHERE column LIKE '%승환';
WHERE column LIKE '_승환';
WHERE column LIKE '%승%';

• 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우

WHERE SUBSTRING(coumn, 1, 1) = 'X';
WHERE DAYOFMONTH(column) = 1

• NON-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우

WHERE column = deterministic_function()

• 데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우)

WHERE char_column = 10

• 문자열 데이터 타입의 콜레이션이 다른 경우

WHERE utf8_bin_char_column = euckr_bin_char_column

• 일반 DBMS에선 NULL 값이 인덱스에 저장되지 않지만 MySQL에서는 NULL 값도 인덱스에 저장됨

-- 다음과 같이 사용 가능
WHERE column IS NULL

INDEX ix_test (column_1, column_2, column_3, column_n)

• 작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우

  • column_1 칼럼에 대한 조건이 없는 경우
  • column_1 칼럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우

• 작업 범위 결정 조건으로 인덱스를 사용하는 경우(i는 2보다 크고 n보다 작은 임의의 값을 의미)

  • column_1 ~ column_(i-1) 칼럼까지 동등 비교 형태("=" 또는 "IN")로 비교
  • column_i 칼럼에 대해 다음 연산자 중 하나로 비교
    • 동등 비교("=" 또는 "IN")
    • 크다 작다 형태(">" 또는 "<")
    • LIKE로 좌측 일치 패턴(LIKE '승환%')

• B-Tree 인덱스라 다른 RDBMS에서도 작동한다.

WHERE column_1 <> 2 -- 인덱스 사용 불가

WHERE column_1 = 1 AND column_2 > 10 -- column_1과 column_2까지 범위 결정 조건으로 사용됨

WHERE column_1 IN (1, 2) AND column_2 = 2 AND column_3 <= 10 -- column1, 2, 3까지 범위 결정 조건으로 사용됨

-- 1, 2, 3 까지 범위 결정 조건
-- 4는 체크 조건으로 사용됨
WHERE column_1 = 1 AND column_2 = 2 AND column_3 IN (10, 20, 30) AND column_4 <> 100

-- 1, 2, 3, 4까지 범위 결정 조건으로 사용
-- 좌측 패턴 일치 LIKE 비교는 크다 또는 작다 비교와 동급으로 생각하면 됨
WHERE column_1 = 1 AND column_2 IN (2, 4) AND column_3 = 30 AND column_4 LIKE '김승%'

-- 1, 2, 3, 4, 5 칼럼 까지 모두 범위 결정 조건으로 사용
WHERE column_1 = 1 AND column_2 = 2 AND column_3 = 30 AND column_4 = '김승환' AND column_5 = '서울'

[xi-jjun]

9/11 스터디

• index란?
• B-Tree 작성중

[JoungMinJu]

8.1 디스크 읽기 방식 ~ 8.3 B-Tree 인덱스

8.1 디스크 읽기 방식

CPU나 메모리와 같은 전기적 특성을 띤 장치의 성능은 짧은 시간 동안 빠른 속도로 발전. BUT 디스크 같은 기계식 장치의 성능은 제한적으로 발전함
-> DB의 성능 튜닝은 어떻게 디스크 IO를 줄이느냐가 관건

(1) HDD와 SSD

기계식 HDD를 대체하기 위해 전자식 저장 매체인 SSD(Solid State Drive)가 많이 출시되고 있음. SSD도 기존 HDD와 같은 인터페이스(SATA, SAS)를 지원하므로 내장 디스크나 DAS 또는 SAN에 그대로 사용할 수 있다.

DAS = direct attached storage. pc나 서버에 꽂아서 사용하는 스토리지(like 외장하드)

SAN = storage area network. 서버와 저장장치를 광채널 switch로 연결한 고속 데이터 네트워크.

SSD는 HDD에서 "데이터 저장용 플래터"를 제거하고, 대신 "플래시 메모리"를 장착하고 있다. 디스크 원판을 기계적으로 회전시킬 필요가 없어서 빨리 데이터를 읽고 쓸 수 있고, 전원이 공급되지 않아도 데이터가 삭제되지 않는다.

SDD는 대부분 기존 HDD보다 용량도 적고 가격도 비싸지만, 예전보다는 SSD가 더 대중화된 상태이며 요즘은 DBMS용으로 사용할 서버에는 대부분 SSD를 채택하고 있다.

디스크 헤더를 움직이지 않고 한 번에 많은 데이터를 읽는 순차 IO에서는 비슷한 성능을 보일 수도 있지만, 기존 HDD보다 랜덤 IO에서 압도적인 성능 차이를 보여준다.

DB 서버의 작업은 대부분 랜덤 IO를 통해 작은 데이터를 읽고 쓰는 작업이므로 SSD의 장점은 DBMS용 스토리지에 최적이라고 볼 수 있다.

(2) 랜덤 IO와 순차IO

순차 IO는 세 개의 페이지를 디스크에 기록하기 위해 "한 번" 시스템 콜을 요청. BUT 랜덤 IO는 세 개의 페이지를 디스크에 기록하기 위해 "세 번" 시스템 콜을 요청했다.

즉, 디스크에 기록해야할 위치를 찾기 위해 순차 IO는 헤드를 한 번 움직였고, 랜덤 IO는 세 번 움직였다

디스크에 데이터를 쓰고 읽는데 걸리는 시간은 디스크 헤더를 움직여서 이동하는 단계에서 결정되기 때문에, 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한 번에 기록하느냐에 의해 결정된다고 볼 수 있다. (DB 대부분의 작업은 이러한 작은 데이터를 빈번히 읽고 쓰기 때문에 MySQL 서버에는 그룹 커밋이나 바이너리 로그 버퍼 또는 InnoDB 로그 버퍼 등의 기능이 내장되어 있다.)

8.2 인덱스란?

컬럼의 값과 해당 레코드가 저장된 주소를 key-value 쌍으로 삼아 인덱스를 만들어 둔다. 그리고 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.

SortedList는 DBMS의 인덱스와 같은 자료구조이며, ArrayList는 데이터 파일과 같은 자료 구조를 사용한다.

SortedList는 저장되는 값을 항상 정렬된 상태로 유지하는 자료 구조이고, ArrayList는 값을 저장되는 순서 그대로 유지하는 자료 구조이다. DBMS의 인덱스도 저장되는 칼럼의 값을 이용해 항상 정렬된 상태를 유지한다. 그리고 데이터 파일은 ArrayList와 같이 저장된 순서대로 별도의 정렬 없이 그대로 저장해 둔다.

SortedList 자료 구조는 데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만 이미 정렬되어있기 때문에 빨리 원하는 값을 찾아올 수 있다. 결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고, 데이터의 읽기 속도를 높이는 기능이다.

인덱스는 **데이터를 관리하는 방식(알고리즘)**과 중복 값의 헝용 여부 등에 따라 여러가지로 나눠볼 수 있다.

우선 인덱스를 역할별로 구분해 본다면 "프라이머리 키"와 "보조 키"로 구분할 수 있다.

• 프라이머리 키는 그 레코드를 대표하는 칼럼(식별자)의 값으로 만들어진 인덱스를 의미한다.
• 프라이머리 키를 제외한 나머지 모든 인덱스는 세컨더리 인덱스로 분류한다.

알고리즘 별로 구분할 경우 많은 분류가 가능하겠지만, 대표적으로는 B-TREE 인덱스와 Hash 인덱스로 구분할 수 있다. (최근에는 Fractal-Tree 인덱스나 로그 기반의 Merge-Tree 인덱스...도 존재)

• B-Tree 알고리즘은 가장 일반적으로 사용되는 인덱스 알고리즘. 원래의 값을 이용해서 인덱싱 하는 알고리즘.
• Hash 인덱스 알고리즘은 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘. 주로 메모리 기반의 DB에서 많이 사용한다.(범위 검색이 불가능)

데이터 중복 허용 여부로 분류하면 유니크 인덱스, 유니크하지 않은 인덱스로 구분할 수 있다.

Fractal-Tree 인덱스 : 독점적인 특허로 등록된 알고리즘. 인덱스 키를 검색하거나 변경하는 과정에서 디스크의 랜덤 IO가 많이 필요하다는 B-Tree의 단점을 최소화하고 이를 순차 IO로 변환해서 처리할 수 있다는 장점을 갖고 있음. (+ B-Tree의 장점도 그대로 갖고 있음)

LSM-Tree(Log-Structured Merge-Tree) : 최신 DB에서 사용하고 있는 인기있는 데이터 구조. LSM Tree는 각각의 기본 저장 매체에 최적화 된 두 개 이상의 개별 구조로 데이터를 유지한다. 메모리에는 실제 디스크의 데이터 값을 포함하는 바이트 오프셋에 대한 참조 정보를 Key-value 형태로 해시 데테이블로 관리한다. LSM-tree의 update는 디스크 I/O를 최소화하기위해 메모리의 버퍼에 로그를 남긴다. 그리고 버퍼는 주기적으로 정렬되어 디스크에 쓰여지는데 이를 flush라고 하며, 정렬된 일련의 배열을 run이라고 한다.

8.3 B-Tree 인덱스

B는 Balanced를 의미한다.

(1) 구조 및 특성

B-Tree는 트리 구조의 최상위에 하나의 "루트노드"가 존재하고 그 하위에 "자식 노드"가 붙어 있는 형태이다.

트리 구조의 가장 하위에 있는 노드를 "리프 노드"라고 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 "브랜치 노드"라고 한다.

인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

"인덱스의 키"값은 모두 정렬되어 있지만, 데이터 파일의 레코드는 정렬되어 있지 않는다. ((+)데이터 파일이 INSERT된 순서대로 저장되는 것은 맞지만, 중간에 레코드가 삭제되어 빈공간이 생기면 거기를 재활용하도록 DBMS가 설계된다고 한다.)

인덱스는 테이블의 키 칼럼만 가지고 있으므로 나머지 칼럼을 읽으려면 데이터 파이라에서 해당 레코드를 찾아야 한다. 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다.

위 그림에선 프라이머리 키가 ROWID의 역할을 한다. InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다고 볼 수 있다. 그래서 InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 데이터 파일을 바로 찾아가진 못한다. 인덱스에 저장되어 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후 프라이머리 키 인덱스의 리프 페이지에 저장되어 있는 레코드를 읽는다. (???) 즉, InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한 번 검색해야 한다.~~ (???)~~

(2) B-Tree 인덱스 키 추가 및 삭제

[1] 인덱스 키 추가

B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다.
리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리되어야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 드는 것으로 알려졌다.

[2] 인덱스 키 삭제

해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크만 하면 작업이 완료된다.
마킹 작업 또한 디스크 IO가 필요한데, MySQL 5.5 이상 버전의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연 처리될 수도 있다.

[3] 인덱스 키 변경

인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 단순히 인덱스상의 키 값만 변경하는 것은 불가능하다.
키 값을 삭제하고 -> 다시 새로운 키 값을 추가하는 형태로 처리된다.
InnoDB 스토리지 엔진을 사용하는 테이블에서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리 될 수 있다.

[4] 인덱스 키 검색

인덱스를 검색하는 작업은 B-Tree의 루트 노드에서부터 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행한다.(=트리 탐색)

B-Tree 인덱스를 이용한 검색은 "100% 일치" 또는 "값의 앞 부분만 일치"하는 경우에 사용할 수 있다. 부등호 비교 조건에서도 인덱스 활용할 수 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로 인덱스를 사용할 수 없다.~~ (???)~~

또한 인덱스 탐색에서 중요한 사실은 인덱스의 키 값에 변형이 가해진 후 비교되는 경우엔 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다는 것이다.

InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스크 키락이 검색을 수ㅅ행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있다. 따라서 UPDATE, DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다. (설계가 중요하다는 뜻을 포함한다.)

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

[1] 인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다.

인덱스도 결국은 페이지 단위로 관리되며, 루트와 브랜치 그리고 리프 노드를 구분한 기준이 바로 페이지 단위이다.

DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조이다.
그렇다면 자식 노드를 몇 개까지 가질까? 이는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다.

인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 더 느려진다.
또한 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미한다. 하지만 인덱스를 캐시해두는 InnoDB의 버퍼 풀의 크기는 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어든다. 그렇게 되면 자연히 메모리의 효율이 떨어지는 결과를 가져온다

[2] B-Tree의 깊이

인덱스 키 값의 크기가 커지면 커질수록 "하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고" 그 때문에 B-Tree의 깊이가 더 깊어져서 디스크 읽기가 더 많이 필요하게 된다.

-> 인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋다!

(사실 B-Tree의 깊이가 5단계 이상까지 깊어지는 경우는 흔치 않다.)

[3] 선택도(기수성)

이는 모든 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다.

인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아진다(선택도도 떨어진다.)

인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

[4] 읽어야 하는 레코드의 건수

"인덱스를 통해 테이블의 레코드를 읽는 것"은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다.

테이블에 레코드가 100만건이 저장되어 있는데, 그 중에서 50만 건을 읽어야하는 쿼리가 있다고 가정해보자.

1. 작업을 모두 읽어서 필요 없는 50만건 버리기
2. 인덱스를 통해 필요한 50만건만 읽어오기

중 무엇이 효율적일지 판단해야 한다.

일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 한 건을 읽는 것이 직접 레코드 한 건을 읽는 것보다 4배 정도 비용이 많이 드는 작업인 것으로 예측한다. 즉, 인덱스를 통해 읽어야할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 읽어서 필터링 하는 것이 효율적이다.

(4) B-Tree 인덱스를 통한 데이터 읽기

MySQL이 인덱스를 이용하는 대표적인 방법 세 가지를 살펴보자.

[1] 인덱스 레인지 스캔

가장 대표적인 방법이고, 나머지 두 개보다는 빠른 방법이다.

SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

인덱스 레인지 스캔은 검색해야할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.
"검색하려는 값의 수"나 "검색 결과 레코드 건수"와 관계없이 레인지 스캔이라고 표현한다.

위의 그림에서도 알 수 있듯,
루트 노드에서부터 -> 브랜치 노드 -> 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점을 찾을 수 있다.

시작해야할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다.

위 그림에서는 B-Tree 인덱스에서 루트와 브랜치 노드를 이용해 스캔 시작 위치를 검색하고, 그 지점부터 필요한 방향으로 인덱스를 읽어나가는 과정을 보여준다. 인덱스 자체의 정렬 특성 때문에 정렬된 상태로 레코드를 가져오게 된다.

여기서 알 수 있듯, 인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다.
이때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어 오는데, 레코드 한 건 한 건 단위로 랜덤 IO가 발생한다.
-> 그래서 인덱스를 통해 레코드를 읽는 작업은 비용이 많은 작업으로 분류된다.

인덱스 레인지 스캔은 크게 세 단계를 거친다.

1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다.(인덱스 탐색)
2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례로 쭉 읽는다. (인덱스 스캔)
3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어 온다.

(쿼리가 필요로 하는 데이터에 따라 3번 과정은 필요하지 않을 수도 있다. 이를 "커버링 인덱스"라고 한다. 커버링 인덱스로 처리되는 쿼리는 랜덤 읽기가 상당히 줄어들고 성능은 그만큼 빨라진다.)

[2] 인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식.
대표적으로 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 이 방식이 사용된다. (ex. 인덱스 = A,B,C 칼럼 // 조회 조건 = B or C 칼럼)

일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로, 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적이다. 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용된다. (데이터 레코드까지 모두 읽어야 한다면 이 방식으로 처리되진 X)

리프 노드의 제일 앞 or 제일 뒤로 이동 -> 인덱스의 리프 노드를 연결하는 링크드 리스트를 따라서 처음부터 끝까지 스캔

[3] 루스 인덱스 스캔

말 그대로 느슨하게 인덱스를 읽는 것이다. (앞의 두 방법은 타이트 인덱스 스캔으로 분류된다.)

이는 인덱스 레인지 스캔과 비슷하게 작동하지만, 중간에 필요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리한다.
GROUP BY나 MAX() MIN() 최적화 하는 경우에 사용된다.

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

해당 테이블이 dept_no와 emp_no로 인덱스가 생성되어 있고, (dept_no, emp_no) 조합으로 정렬되어 있기 때문에, dept_no 그룹별로 첫 번째 레코드의 emp_no 만 읽으면 된다.
그래서 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동하면 되는 ! 루스 인덱스 스캔이 가능해진다.

[4] 인덱스 스킵 스캔

employees 테이블에 다음과 같은 인덱스를 생성해보자.

ALTER TABLE employees
AND INDEX ix_gender_birthdate (gender, birthdate);

이 인덱스를 사용하면 WHERE 조건절에 gender 칼럼에 대한 비교 조건이 필수이다.

SELECT * FROM employees WHERE birth_date >='~';

-> 인덱스 사용하지 못하는 쿼리

SELECT * FROM employees WHERE gender = 'M' AND birth_date >= '~';

-> 인덱스 사용할 수 있는 쿼리

주로 첫 번째 쿼리와 같은 케이스에서는 birth_date 칼럼부터 시작하는 인덱스를 새로 생성해야만 했다.

근데 MySQL 8.0 버전부터는 옵티마이저가 birth_date 칼럼만으로도 인ㄷ게스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입되었다.

이렇게 되면 gneder 칼럼에서 유니크한 값을 모두 조회해서 주어지 누커리에 gender 칼럼의 조건을 추가해서 쿼리를 다시 실행하는 형태로 처리한다.

새로이 도입된 기능인 인덱스 스킵 스캔은 아직 아래와 같은 단점이 존재한다.

1. WHERE 조건절에 조건이 없는 인덱스의 "선행 칼럼"의 "유니크한 값 개수"가 적어야함.
   -> 성능 저하가 발생할 수 있기 때문에

2. 쿼리가 인덱스에 존재하는 칼럼만으로 처리가 가능해야 한다.(커버링 인덱스)
   -> SELECT * FROM employees WHERE birth_date >= '~'; 의 경우엔 다른 컬럼도 어차피 다 조회해야하기 때문에 스킵 스캔 사용하지 못하고 풀 테이블 스캔으로 넘어가게 된다.

(5) 다중칼럼 인덱스

두 개 이상의 컬럼으로 구성된 인덱스를 의미한다.
다중 칼럼 인덱스에서는 인덱스 내에서 각 칼럼의 위치가 상당히 중요하다.

(6) B-Tree 인덱스의 정렬 및 스캔 방향

[1] 인덱스의 정렬

MySQL 8.0 버전부터는 정렬 순서를 혼합한 인덱스도 생성할 수 있게 됐다.

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

<1> 인덱스 스캔 방향
first_name 칼럼에 대한 인덱스가 포함된 employees 테이블에 대해 다음 쿼리를 실행하는 과정을 살펴보자.

SELECT *
FROM employees
ORDER BY first_name DESC
LIMIT 1;

옵티마이저는 이 경우에 역순으로 접근해 첫 번째 레코드만 읽으면 된다는 것을 알고 있다.

쿼리가 인덱스를 읽는 방향에 따라 정렬 효과를 달리 얻을 수 있다는 것이다.

<2> 내림차순 인덱스

• 오름차순 인덱스 : 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스

• 내림차순 인덱스 : 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스

• 인덱스 정순 스캔 : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔

• 인덱스 역순 스캔 : 인덱스 키의 크고 작업에 관계 없이 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

내림차순 인덱스의 필요성에 대해 설명하기 위해 테스트용 테이블을 생성하고 1천만건 정도의 레코드를 준비해보자

CREATE TABLE t1 
(tid INT NOT NULL AUTO_INCREMENT,
 TABLE_NAME VARCHAR(64),
 COLUMN_NAME VARCHAR(64),
 ORDINAL_POSITION INT,
 PRIMARY KEY(tid)
 ) ENGINE = InnoDB;

INSELRT INTO t1
SELECT NULL, TABLE_NAME, COLUMN_NAME, ORDINAL_POSITION
FROM information_schema.COLUMNS;

INSERT INTO t1
SELECT NULL, TABLE_NAME, COLUMN_NAME, ORDINAL_POSITION
FROM t1;

...

이 테이블을 풀 스캔하면서 정렬만 수행하는 쿼리를 실행해보자.
아래의 두 쿼리는 테이블의 프라이머리 키를 asc 또는 desc로 스캔하면서 마지막 레코드 한 건만 반환한다. 하지만 LIMIT .. OFFSET... 부분의 쿼리로 인해 실제 MySQL 서버는 테이블의 모든 레코드를 스캔해야 한다.

SELECT * FROM t1 ORDER BY tid ASC LIMIT 12619775,1;

-> 4.15sec

SELECT * FROM t1 ORDER BY tid DESC LIMIT 12619775, 1;

-> 5.35sec

InnoDB에서 인덱스 역순 스캔이 인덱스 정순 스캔에 비해 느릴 수밖에 없는 다음의 두 가지 이유가 있다.

1. 페이지 잠금이 인덱스 정순 스캔에 적합한 구조
2. 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조

내림차순과 오름차순 인덱스의 내부적인 차이로 인한 성능을 살펴봤다. 이제 서비스 요건에 맞게 어떤 정렬 순서의 인덱스를 선택해야 할지 살펴보자. 일반적으로 인덱스를 ORDER By .. DESC 하는 쿼리가 소량의 레코드에 드물게 실행되는 경우라면 내림차순 인덱스를 굳이 고려할 필요는 없어보인다. (???)

(7) B-Tree 인덱스의 가용성과 효율성

[1] 비교 조건의 종류와 효율성

다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등 비교인지 아니면 크다 또는 작다 같은 범위 조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라지며, 그 효율 또한 달라진다.

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

이 쿼리를 위해 dept_emo 테이블에 각각 칼럼의 순서만 다른 두 가지 케이스로 인덱스를 생성했다고 가정하자. 위의 쿼리가 처리되는 동안 각 인덱스에 어떤 차이가 있었는지 살펴보자.

1. INDEX(dept_no, emp_no)
2. INDEXD(emp_no, dept_no)

1번의 경우 dept_no = 'd002 AND emp_no >= 10144인 레코드를 찾고, 그 이후에는 dept_no가 'd002'가 아닐 때까지 인덱스를 그냥 쭉 읽기만 하면 된다.

하지만 2번의 경우 emp_no >= 10144 AND dept_no = 'd002'인 레코드를 찾고 그 이후 모든 레코드에 대해 dept_no가 'd002'인지 비교하는 과정을 거쳐야 한다.

[2] 인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬되어 있다는 것이다.
인덱스 키 값의 정렬만 표현하지만 사실은 인덱스 키 값의 이런 정렬 특성은 빠른 검색의 전제 조건이다. 즉 하나의 칼럼으로 검색해도 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능하다. 또한 다중 칼럼 인덱스에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다.

[3] 가용성과 효율성 판단

B-Tree 인덱스의 특성상 다음 조건에서는 사용할 수 없다.

다중 칼럼의 경우는 다음과 같다.
아래와 같은 다중 칼럼이 있다고 하면

위 두 가지 조건을 모두 만족하는 쿼리는 column_1 부터 column_i까지는 작업 범위 결정 조건으로 사용되고
column_(i+1)부터 column_n까지는 체크 조건으로 사용된다.

인덱스를 사용하는 경우와 그렇지 않은 상황에 해당하는 쿼리의 조건 몇 가지를 예제로 살펴보자.

[rawfishthelgh]

인덱스 개념
B-Tree