데이터베이스 인덱스
데이터베이스도 컴퓨터의 하드 디스크(HDD, SSD)에 데이터를 쓰거나 적는다.
랜덤 IO와 순차 IO
하드 디스크 드라이브에 접근하려면 플래터를 돌려서 데이터가 저장된 위치로 헤더를 이동시켜서 데이터를 읽는다. 랜덤 IO는 읽어야 할 데이터의 위치가 흩어져있어서 헤더를 여러번 이동해야 한다. 반면 순차 IO는 읽어야할 데이터의 위치를 딱 한번만 움직이고 연속해서 데이터를 읽으면 된다. 그래서 순차 IO가 랜덤 IO보다 유리하다.
하지만 쿼리를 튜닝한다고 해서 랜덤 IO를 순차 IO로 바꿀 수는 없다. 대신 쿼리를 튜닝해서 랜덤 IO를 줄이는 쪽으로 최적화한다.
인덱스 레인지 스캔과 풀 테이블 스캔
그럼에도 랜덤 IO와 순차 IO 개념을 알아야 하는 이유는 인덱스 레인지 스캔과 풀 테이블 스캔을 선택하는 판단 기준이 되기 때문이다. 인덱스 레인지 스캔은 랜덤 IO이고 풀 테이블 스캔은 순차 IO이다. 읽어야 할 데이터가 적은 경우에는 인덱스 레인지 스캔이 훨씬 유리하지만 읽어야 할 데이터가 많은 경우는 랜덤 IO로 인덱스 레인지 스캔하는 것보다 순차 IO로 풀 테이블 스캔하는 것이 더 낫다.
인덱스
특정 데이터를 조회할 때 테이블 전체를 스캔해서 찾는 것보다 빠르게 접근할 수 있는 인덱스를 활용한다. 인덱스는 특정 칼럼과 해당 데이터가 저장된 주소를 키-값 쌍 형태로 저장된다. 그리고 인덱스는 조건에 해당하는 칼럼을 빠르게 조회할 수 있도록 칼럼에 따라 정렬되어 있다.
문제는 데이터가 추가됐을 때 인덱스의 적절한 위치에 데이터를 등록해줘야 한다. 데이터가 삭제되거나 인덱스의 키값으로 활용되는 칼럼이 수정되어도 비슷한 과정을 거치게 된다. 결론적으로 인덱스는 저장(insert, delete, update) 성능을 포기하는 대신 조회 성능을 높이는 방법이다.
B-Tree 인덱스
MySQL은 B-Tree 인덱스와 해시 기반 인덱스를 사용한다.
B-Tree는 기본적으로 세가지 리프로 나눌 수 있다.
- 루트 노드 : 최상단 노드
- 리프 노드 : 가장 하위 단계에 있는 노드
- 브랜치 노드 : 트리 중 루트 노드와 리프 노드를 제외한 노드
각 노드에는 여러 키-값 쌍의 데이터를 가지고 있다. 루트노드와 브랜치 노드는 값을 자식 노드의 주소를 가지고 있다. 리프 노드는 값으로 프라이머리키를 가진다. 이 프라이머리 키로 실제 데이터 파일에 접근할 수 있게 된다. MyISAM 스토리지 엔진은 값으로 프라이머리 키 대신 레코드 주소값(offset, insert 순번)을 저장해서 접근한다.
InnoDB 기반인 경우에는 프라이머리 키 인덱스를 활용해서 데이터에 접근하게 된다. 즉 InnoDB 스토리지 엔진을 사용하는 경우에는 프라이머리 키 인덱스를 한번 더 탐색해야 한다.
B-tree 인덱스 추가
인덱스는 특정 칼럼이 정렬되어야 한다. 그래서 데이터 추가 시 적절한 노드에 삽입하게 되는데 만약 해당 노드에 이미 자식 노드가 가득 차있다면 노드를 분리해야 한다. 이 과정은 상위 노드에도 영향이 갈 수 있다. InnoDB는 인덱스 추가 작업을 지연시켜서 나중에 한다. 하지만 프라이머리 키나 유니크 인덱스의 경우는 유일성 확인을 해야 하기 때문에 즉시 처리한다.
B-tree 인덱스 삭제
해당 키값이 저장된 노드를 삭제 마킹을 하고 방치하거나 필요한 경우 재활용할 수 있다. 삭제 마킹 작업도 MySQL 5.5 이후의 Innodb 스토리지 엔진에서 지연 되어 처리할 수 있다.
B-tree 인덱스 변경
인덱스 키값만 변경할 수 없다. 해당 키를 가진 노드를 제거하고 변경된 키값으로 추가하는 방식으로 수행한다.이 작업 또한 InnoDB에서 체인지 버퍼에서 기록해놨다가 지연 처리할 수 있다.
B-tree 인덱스 검색
B-tree 인덱스를 검색할 때는 루트 노드부터 최종 리프 노드까지 이동하면서 비교 작업을 통해 데이터를 검색한다. B-tree 인덱스를 검색할 때는 값의 앞 부분만 일치하는 경우에는 가능하다. 하지만 값의 뒷 부분만 검색하는 경우는 B-tree를 활용한 검색이 불가능하다. 왜냐면 B-tree 인덱스는 정렬되어서 저장하는데 이 정렬 기준이 값의 앞 부분부터 적용되기 때문이다. 그리고 함수나 연산을 수행한 결과로 검색할 수 없다. 예를 들면 where fun(idx) > 10 이런 조건문은 사용할 수 없다. 왜냐면 fun(idx) 를 알아내기 위해서는 모든 인덱스 키값을 함수에 적용해봐야 하기 때문이다.
InnoDB의 인덱스와 락
InnoDB에서는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠그고 레코드를 잠근다. 만약 적절한 인덱스가 없는 경우에는 불필요하게 여러 레코드를 잠글 수 잇다.
인덱스 키 값의 크기와 깊이
인덱스의 노드도 페이지로 관리된다. RDBMS의 B-tree 노드의 자식 노드 갯수는 가변적이다. 자식 노드 갯수는 인덱스 페이지의 크기와 키값의 크기로 정해진다. 즉 페이지 크기 / (인덱스 키 크기 + 자식 노드 주소 크기) = 한 노드의 자식노드 갯수 이 공식을 통해 노드 갯수를 구할 수 있다. 이 경우 페이지 크기를 높이거나 인덱스 키를 줄이면 자식노드 갯수를 늘릴 수 있게 된다.
한 노드에서 자식노드 갯수를 늘리면 여러 인덱스 페이지를 읽지 않아도 된다. 그리고 키 값이 커지면 인덱스 전체의 크기가 커지므로 인덱스를 캐시해두는 InnoDB 버퍼 풀에 캐시되는 데이터가 적어지게 된다. 인덱스 페이지에 자식 노드 갯수가 줄어드는 것은 결론적으로 B-tree의 깊이가 깊어진다는 것을 의미하고 이는 읽어야 할 인덱스 페이지가 많아진다.
인덱스의 선택도(기수성)
인덱스 키 값 중 유니크한 값의 수를 의미한다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 더 빠르게 처리된다. 다만 정렬이나 그룹핑을 위해서 인덱스를 만드는 것이 좋다.