1. 인덱스의 의미
컬럼(들)의 값과 해당 레코드가 저장된 주소를 같이 저장하여 인덱스를 만든다.
SotedList 자료구조로 데이터가 정렬된 구조로 저장하여 인덱스가 많은 테이블은 Insert, Update, Delete 문장의 처리가 느려진다.
인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다.
1-1. 인덱스를 역할별로 구분
- Primary Key : 테이블에서 해당 레코드를 식별할 수 있는 기준값으로 Unique해야 하며 Not null 이어야 한다.
- Secondary Index : Primary Key를 제외한 나머지 모든 인덱스를 보조 인덱스로 분류한다. Unique Index는 대체키로 분류하기도 하고 보조 인덱스로 분류 하기도 한다.
1-2. 데이터 저장 방식(알고리즘)
- B(alanced)-Tree 알고리즘 : B-Tree 인덱스는 컬럼의 값을 변형하지 않고, 원래의 값을 이용해서 인덱싱
- Hash 인덱스 알고리즘 : 컬럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘, 등호(=) 조건 일때만 사용 가능
- Fractal-Tree 알고리즘 : B-Tree의 단점을 보완하기 위해 고안된 알고리즘. 값을 변형하지 않고 인덱싱하며 데이터가 저장되거나 삭제될 때 처리 비용을 상당히 줄일 수 있게 설계된 것이 특징
1-3. 데이터 중복여부
- Unique Index : 항상 동등 조건으로 검색하고 1건의 레코드만 찾음
- Non-Unique Index : 같은 값이 1개 이상 존재 할 수 있는 인덱스
2. B-Tree Index
2-1. 구조 및 특징
최상위에 하나의 루트 노드가 존재하고 중간 노드를 브랜치 노드 젤 하위 노드를 리프 노드라 한다. 인덱스의 리프노드는 항상 실제 데이터 레코드를 찾아가기 위한 레코드의 주소 값을 가진다.
레코드 주소는 DBMS종류나 MySQL의 스토리지 엔진에 따라 의미가 달라진다. 오라클은 물리적인 레코드 주소(rowid)가 되지만 MyISAM 테이블에서는 내부적인 레코드의 아이디(번호)를 의미한다. 그리고 InnoDB 테이블은 Primary Key에 의해 클러스터링되기 때문에 Primary Key 값 자체가 주소 역할을 한다. MySQL 테이블의 인덱스는 인덱스컬럼값+주소값(InnoDB의 PK or MyISAM의 레코드 아이디값)이 인덱스 레코드로 구성된다.
데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임의의 순서대로 저장된다. 하지만 InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 Primary Key 순서대로 정렬되어 저장된다. 오라클의 IOT(Index Organized Table)나 MS-SQL의 클러스터 테이블과 같은 구조를 말한다. 다른 DBMS에서는 클러스터링 기능이 선택사항이지만, InnoDB에서는 디폴트로 클러스터링 테이블이 생성된다. 클러스터링이란 비슷한 값을 최대한 모아서 저장하는 방식이다.
2-2. 인덱스키 추가 및 삭제
인덱스의 새로운 키 값이 B-Tree에 저장될 때는 저장될 키값을 이용해 저장될 위치를 검색하여 인덱스의 키값과 대상 레크드의 주소 정보를 B-Tree의 리프노드에 저장된다. 리프노드에 더이상 저장 할 수 없을 때는 리프 노드가 Split돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다.(비용이 발생)
인덱스 추가로 인한 INSERT나 UPDATE문장에 끼치는 영향을 살펴보자. 일반적으로 테이블에 B-Tree 인덱스가 3개 있다면 테이블에 인덱스가 하나도 없을때 비용이 1이고, 3개인 경우에는 5.5(1.5*3+1) 정도의 비용이 든다고 예측할 수 있다. 이 비용의 대부분이 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 하기 때문에 시간이 오래 걸린다.
MyISAM 스토리지 엔진은 "delay-key-write" 파라미터 설정해 인덱스 키 추가 작업을 지연 처리할 수 있는데 이는 동시 작업 환경에서는 적합하지 않다. InnoDB 스토리지 엔진은 상황에 따라 인덱스 키 추가 작업을 지연시킬지 바로 처리할지 결정한다.
[Insert Buffer의 처리 방식]
1) 사용자 쿼리 실행
2) InnoDB 버퍼 풀에 새로운 키값을 추가해야 할페이지(B-Tree의 리프 노드)가 존재한다면 즉시 키 추가 작업 처리
3) 버퍼 풀에 B-Tree의 리프 노드가 없다면 인서트 버퍼에 추가할 키값과 레코드의 주소를 임시로 기록해 두고 작업 완료(사용자의 쿼리는 실행 완료됨)
4) 백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 머지해야 할 인덱스 키값이 있는지 확인한 후, 있다면 병합함(B-Tree에 인덱스 키와 레코드의 주소(PK)값을 저장)
5) 데이터베이스 서버 자원의 여우가 생기면 MySQL 서버의 인서트 버퍼 머지 스레드가 조금씩 인서트 버퍼에 임시 저장된 인덱스 키와 주소 값을 머지(B-Tree에 인덱스키와 주소값을 저장)시킴
인서트 버퍼는 MySQL 5.1이하에서는 INSERT로 인한 인덱스 키 추가 작업만 버퍼링 및 지연처리 함.
MySQL 5.5 이상의 버전에서는 INSERT뿐 아니라 DELETE등에 의한 인덱스 키의 추가 및 삭제 작업까지 버퍼링해서 지연 처리하여 Change Buffering이라 한다. 관련 설정 파라미터 "innodb_change_buffering" 설정 값을 이용해 키 추가 작업과 키 삭제 작업중 어느 것을 지연 처리할지 설정한다.
인덱스 키 삭제는 B-Tree의 리프 노드를 찾아서 삭제 마크를 하면 작업이 완료 된다. 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 디스크 I/O 작업이다. MySQL 5.5이상 버전의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연 처리할 수 있다. MyISAM 이나 Memory 스토리지 엔진의 테이블에서는 인서트 버퍼와 같은 기능이 없으므로 인덱스 키 삭제가 완료된 후 쿼리 실행이 완료된다.
인덱스 키 변경시 B-Tree의 키값 변경 작업은 먼저 키값을 삭제한 후, 다시 새로운 키값을 추가하는 형태로 처리된다.
인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프노드까지 이동하면서 비교 작업을 수행한다. 이 과정을 트리 탐색(Tree Traversal)이라고 한다.
B-Tree 인덱스를 이용한 검색은 = 조건이나(100%일치) 또는 값의 앞부분(Left_most part)만 일치하는 경우에 사용할 수 있다. 부등호(<>) 비교나 값의 뒷부분이 일치하는 경우에는 B-Tree 인덱스를 이용한 검색이 불가능하다.
또한, 인덱스 키값에 변형이 가해지면 B-Tree 검색을 사용할 수 없다. 변형된 값은 B-Tree 인덱스에 존재하는 값이 아니다.
InnoDB 스토리지 엔진에서 인덱스는 더 중요한 의미를 가진다. InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키 락(갭 락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있다. 따라서 UPDATE나 DELETE문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없다면 불필요하게 많은 레코드를 잠근다.
2-3. 인덱스 키값의 크기
InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본적인 단위를 페이지(Page) 또는 블록(Block)이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 또한 페이지는 버퍼풀에서 데이터를 버퍼링하는 기본 단위이다. 인덱스도 결국 페이지 단위로 관리된다.
InnoDB의 모든 페이지 크기는 16KB로 고정돼 있다(이를 변경하려면 소스 컴파일이 필요함) 인덱스의 키가 16바이트라 가정하고 자식노드 주소는 데략 6-12바이트로 평균적으로 12바이트로 구성된다고 가정하자. 하나의 인덱스 페이지(16KB)에 16*1024/(16+12) = 585개 저장 할 수 있다. 이 경우에 자식 노드를 585개 가질 수 있는 B-Tree가 된다.
키값의 크기가 두 배인 32바이트로 늘었다고 가정한다면 한 페이지에 인덱스 키를 16*1024/(32+12) = 372개 저장할 수 있다. SELECT 쿼리가 레코드 500개를 읽어야 한다면 전자는 인덱스 페이지 1개로 해결 될 수도 있지만 후자는 최소한 2번 이상의 페이지를 디스크로부터 읽어야 한다.
인덱스를 구성하는 키값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고 그만큼 느려진다. 또한, 인덱스 키 값의 길이가 길어진다는 것은 인덱스의 크기가 커진다는 것을 의미한다. 인덱스를 캐시해 두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리(버퍼 풀 이나 키 캐시)에 캐시해 둘 수 있는 레코드의 수는 줄어들어 메모리의 효율이 떨어지게 된다.
2-4. B-Tree 깊이
B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 인덱스 키값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키값의 개수가 작아지고, 그 때문에 같은 레코드 건수라 하더라도 B-Tree의 깊이(Depth)가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.
인덱스 키값의 크기는 가능하면 작게 만드는 것이 좋다 실제로는 아무리 대용량의 데이터베이스라도 B-Tree의 깊이가 4-5이상까지 깊어지는 경우는 거의 발생하지 않는다.
'MySQL > MySQL' 카테고리의 다른 글
| 해시알고리즘, 해시인덱스 (0) | 2024.12.06 |
|---|---|
| INDEX 엑세스 조건 (0) | 2024.12.06 |
| MySQL의 격리 수준 (0) | 2024.12.06 |
| 트랜잭션 격리 수준과 잠금 (0) | 2024.12.06 |
| 인덱스와 잠금 (0) | 2024.12.06 |