Index 란?
- 데이터베이스 쿼리의 성능을 언급하기위해 빼놓을 수 없는 부분이다. 책의 마지막에 있는 "찾아보기"가 인덱스에 비유된다면 책의 내용은 데이터 파일이라고 볼 수 있다. 책의 "찾아보기" 와 DBMS 인덱스의 공통점 가운데 중요한 것은 정렬이다. 책의 찾아보기도 내용이 많아지면 원하는 검색어를 찾아내는데 시간이 걸린다. 그래서 최대한 빨리 찾을 수 있게 "ㄱ", "ㄴ" , "ㄷ" ..과 같은 순서로 정렬되어 있다. DBMS의 인덱스도 마찬가지로 컬럼의 값을 주어진 순서로 미리 정렬해서 보관한다. 인덱스는 데이터베이스 테이블의 검색 성능을 향상시켜주도록 도와주는 자료구조이다.
- SortedList는 DBMS의 인덱스와 같은 자료 구조이다. 데이터가 저장될 때마다 항상 값을 정렬함으로 저장하는 과정이 느리다, 하지만 정렬이 되어있어서 조회하는 경우에는 매우 빠르다. 쉽게 말해 SELECT를 위해서 INSERT,UPDATE,DELETE의 성능을 희생하는 것이다. 테이블에 인덱스를 추가할 때 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지에 중점을 둬야한다, 무턱대고 인덱스를 추가하면 데이터 저장 성능이 떨어져 인덱스의 크기만 커져 성능이 안좋아 질 수 있다.
B-Tree Index 구조
- 데이터베이스 인덱싱 알고리즘 가운데 가장 일반적이며 범용적으로 사용한다. B-Tree에 B는 Binary가 아닌 Balanced를 의미한다.
- 밑에 그림과 같이 루트 노드 처럼 키 값은 모두 정렬돼 있지만 오른쪽의 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다. 데이터의 순서는 INSERT된 순서대로 저장되지 않는다. 레코드가 삭제되어 빈 공간이 생기면 그 다음의 INSERT는 가능한 삭제된 공간을 재활용하도록 DBMS가 설계되기 떄문에 항상 INSERT된 순서로 저장되는것은 아니다.
- 최상위에 루트노드(Root node)가 있다. 트리 구조에서 가장 하위에 있는 노드를 리프 노드(Leaf node)가 있다. 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 "브랜치 노드(Branch node)"라고 한다. 데이터 베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.
Index 키 추가
- B-Tree에 저장시 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색한다.
- 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다. (리프 노드가 꽉 찬 경우는 리프 노드가 분리 되면서 상위 브랜치 노드까지 처리의 범위가 넓어진다.)
Index 비용 계산법
- 인덱스 키를 추가시 INSERT/UPDATE 속도의 영향을 받는다. 대략 계산시, 테이블에 레코드를 추가하는 작업 비용이 1이라면 테이블에 인덱스에 키를 추가하는 작업 비용은 1.5정도이다. 만약 한 테이블에 인덱스가 3개인 경우라면 (1.5 *3 +1)로 5.5정도의 비용이 예측된다. 이 시간은 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야해서 걸리는 시간이다.
Index 키 삭제
- 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료.
- 후에 삭제 마킹된 인덱스 키 공간을 재활용한다. ( 디스크 I/O 처리가 필요하다.)
Index 키 변경
- 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다. (InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리 될 수 있다.)
Index 키 검색
- B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행한다. 이 과정을 트리 탐색이라한다. 인덱스 트리 탐색은 SELECT에서만 사용하는 것이 아니라 UPDATE/DELETE에서도 처리하기 위해 레코드를 검색할 때도 사용된다.
- 100% 일치하는 값 또는 값의 앞부분만 일치하는 경우(LIKE "example%")에 사용할 수 있다. 부등호 (<,>) 비교 조건에서 사용할 수 있다.
- 인덱스를 구성하는 키 값의 뒷부분(LIKE "%example")만 검색하는 용도로는 사용할 수 없다 또한, 함수나 연산을 수행한 변형된 결과로 정렬하거나 검색하는 작업도 사용할 수 없다.
B-Tree 인덱스 사용에 영향을 미치는 요소
- B-Tree 인덱스는 인덱스를 구성하는 칼럼의 크기와 레코드의 건수, 그리고 유니크한 인덱스 키 값의 개수 등에 의해 검색이나 변경작업의 성능이 영향을 받는다.
- 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라 한다. 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 인덱스도 결국은 페이지 단위로 관리되며 루트와 브랜치, 그리고 리프 노드를 구분한 기준이 바로 페이지 단위이다.
Index 키 값의 크기
- 인덱스의 페이지 크기와 키 값의 크기에 따라 B-Tree의 자식 노드가 결정된다.
- 인덱스 페이지의 기본 값은 16KB이다. 위에 그림처럼 자식 노드에 여러가지 복합적인 정보가 담겼다. 편의상 위의 주소 영역이 평균적으로 12바이트로 구성된다는 가정하에 하나의 인덱스 페이지(16KB)에 몇 개의 키를 저장할 수 있을까?
- 16 * 1024(16+12) = 585개가 저장될 수 있다. 최종적으로 585개의 자식 노드를 가질 수 있다. 만약 인덱스의 값이 두배인 32바이트로 늘어났을 때는 16 * 1024(32+12) = 372개다.
- 위의 계산대로라면 SELECT쿼리가 레코드 500개를 읽어야된다면 페이지가 16KB일때는 한번으로 가능하지만 32KB일때는 두번을 읽어야한다. 결국 인덱스를 구성하는것은 키 값의 크기가 커지며 디스크로부터 읽어햐하는 횟수가 늘어나고, 그만큼 느려진다.
읽어야 하는 레코드의 건수
- 한 테이블에 레코드가 100만 건이 저장돼 있는데, 그 중에서 50만건을 읽어야하는 쿼리가 있다고 가정해보자. 이작업은 전체 테이블을 모두 읽어서 필요없는 50만 건을 버리는 것이 효율적인지, 인덱스를 통해 필요한 50만 건만 읽어 오는 것이 효율적인지 판단해야한다.
- 일반적인 DBMS의 optimizer는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업이다. 즉, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는(필터링)방식으로 처리하는 것이 효율적이다.
- 전체 100만건의 레코드 가운데 50만건을 읽어야한다면 인덱스의 손익 분기점인 20~25%보다 훨씬 크기떄문에 MySQL optimizer는 인덱스를 이용하지않고 직접 테이블을 처음부터 끝까지 읽어서 처리할 것이다.
