[데이터베이스] B-Tree 인덱스 사용에 영향을 미치는 요인

1. 인덱스 키 값의 크기

디스크에 데이터를 저장하는 기본 단위를 페이지 또는 블록이라 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 단위가 된다. 

인덱스는 페이지 단위로 관리된다. 인덱스의 B-Tree는 자식 노드의 개수가 가변적인 구조이다. 그리고 자식 노드의 개수가 페이지의 크기와 값에 의해

결정된다. 인덱스의 키값을 16바이트, 자식 노드의 주소를 12바이트, 하나의 인덱스 페이지를 16KB 라고 한다면, 16 * 1024 / (16 + 12) = 585개의 인덱스를

저장할 수 있다. 그렇다면 인덱스 키의 값을 두배로 늘린다고 하면, 16 * 1024 / (32 + 12) = 372개 저장할 수 있게 된다.

만약에 SELECT 쿼리가 500개의 데이터를 읽는다고 한다면, 페이지의 크기가 16KB일 때, 하나의 인덱스 페이지만 읽으면 되지만, 32KB일 때는 두개의 인덱스

페이지를 읽어야만 한다. 결국은 디스크가 읽어야하는 횟수가 증가된 것이다.

그리고 인덱스 키 값이 증가되면 캐시에 저장할 수 있는 인덱스의 갯수 또한 줄어든다. 결국은 메모리의 효율도 떨어질 수 있다는 것이다.

요약하자면, 인덱스 키 값의 크기가 증가하면, 페이지 내의 인덱스의 갯수가 줄어들고, 디스크를 읽어야할 횟수가 증가하며, 캐시에 저장할 수 있는 인덱스의 

갯수도 줄어든다는 것이다.

2. B-Tree 깊이

인덱스 키 값의 크기가 증가하면, 하나의 페이지 내에서 저장할 수 있는 인덱스가 줄어들고, B-Tree의 깊이도 증가한다. 깊이가 증가하면, 디스크를 읽는 횟수 

또한 증가된다는 것을 의미한다. 아무리 대용량 데이터라 할지라도, 깊이가 4 ~ 5 이상 증가하지 않는다.

3. 선택도 (기수성)

선택도는 인덱스에서 유니크한 키의 갯수를 의미한다. 예를들어, 전체 인덱스 100개 중에서 유니크한 키값이 10개라면 기수성은 10이다.

인덱스의 기수성이 높아질 수록 (유니크한 키 값의 수가 많을 수록) 검색 대상이 줄어들기 때문에 검색의 속도가 증가된다. 

이부분이 이해가 잘 되지 않았지만 쿼리를 통해 예를 들어보자. 쿼리 : SELECT * FROM TBL WHERE COUNTRY = 'KR' AND CITY = 'ILSAN'

여기서 COUNTRY는 인덱스에 해당하고 10000개의 데이터에 대해 COUNTY 인덱스의 유니크가 10개인 경우와 1000개인 경우를 비교해보자

 (1) 10개인 경우

 10개인 경우에는 서로 다른 나라가 10개가 있다는 것을 의미한다. 데이터베이스는 인덱스의 유니크한 인덱스가 몇 종류가 있고, 각각 몇개가 있는지에 대한

 통계 정보를 가지고 있다. 대략적으로 COUNTRY가 KR에 해당하는 데이터가 1000개 정도 된다고 하면, CITY가 ILSAN이라는 것을 찾으려면 1000개의 

 데이터에서 조회를 해야한다. 단 한개의 데이터를 검색하기 위해 불필요한 999개가 존재한다는 것이다. 

 (2) 1000개인 경우

 1000개인 경우에는 서로 다른 나라가 1000개 존재하고, 각 나라의 지역은 약 10개 정도 있다는 것이다. 그렇다면 KR 이며 ILSAN 이라는 데이터를 찾을 때

 10개중 단 9개만이 불필요한 데이터라는 것이다. 

지금은 적은양의 데이터를 비교했지만, 100만개 이상의 대량의 데이터라고 한다면, 엄청난 차이가 있을 것이다. 

4. 읽어야하는 레코드의 수

인덱스를 통해 레코드를 읽는 것은 인덱스를 거치지 않고 바로 데이터를 읽는 것보다 비용이 많이 발생한다. 그렇기 때문에 데이터를 조회할 때, 인덱스를 

거치지 않을지에 대한 선택이 필요하다. 인덱스를 통해 읽어야할 데이터가 전체 데이터의 20 ~ 25%를 넘으면 인덱스를 거치지 않고 전체 데이터를 조회한 

후에 필요하지 않는 데이터를 필터링 하는 것이 더 효율적이다. 예를들어, 10만개 중에서 3만개의 데이터를 조회해야 한다면, 10만개 모두 조회하고, 7만개는 

특정 조건으로 필터링 하는 것이 더 효율적이라는 것이다!