B-Tree 인덱스를 구성하는 컬럼의 크기와 레코드의 건수, 그리고 유니크한 인덱스 키값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향을 받는다.
InnoDB 스토리지 엔진은 디스크에 저장하는 가장 기본 단위를 페이지 또는 블록이라고하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 단위가 된다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도하다.
인덱스는 결국은 페이지 단위로 관리되며, 루트 - 브랜치 - 리프 노드를 구분한 기준이 페이지 단위다.
이진 트리는 각 노드가 자식 노드를 2개만 가지는데, 만약 DBMS의 B-TREE가 이진 트리라면 이덱스 검색이 상당히 비효율적일 것이다. 일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조다. B-Tree의 자식노드 갯수는 페이지 크기와 키 값의 크기에 따라 결정된다. 만약 인덱스 키가 16바이트라고 가정하면 아래 그림과 같이 인덱스 페이지가 구성될 것이다.
자식 노드 주소라는 것은 여러 가지 복합적인 정보가 담긴 영역이며, 페이지의 종류별로 대략 6바이트 에서 12바이트까지 다양한 크기의 값을 가질 수 있다.
위 그림의 경우, 하나의 인덱스 페이지(16KB)에 몇 개의 키를 저장할수 있을까? 계산해보면 16 * 1024 / (16 + 12) = 585개를 저장할 수 있다.
인덱스 키 값이 커지면 읽어야 하는 범위가 커지게 되며, 그 만큼 느려진다.
또한 인덱스 키값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미한다. 하지만 인덱스를 캐시해두는 InnoDB의 버퍼풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 떄문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어드는 것을 의미한다. 그러면 자연스럽게 메모리의 효율이 떨어지게 되는 결과를 가져온다.
B-Tree 인덱스의 깊이는 상당히 중요하지만 직접적으로 제어할 방법은 없다.
여기서는 인덱스 키값의 평균 크기가 늘어나면 어떤 현상이 추가로 더 발생하는지 알아보자. B-Tree의 깊이가 3인 경우 최대 몇 개의 키값을 가질 수 있는지 한번 비교해보자. 키 값이 16바이트인 경우에는 최대 2억(585 * 585 *585)개 정도의 키값을 담을 수 있지만 키값이 32 바이트로 늘어나면 5천만 개로 줄어든다. B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 결론적으로 인덱스 키값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키값의 개수가 작아지고, 그 때문에 같은 레코드 건수라 하더라고 B-Tree의 깊이가 깊어져 디스크 읽기가 더많이 필요하게 된다.
*__ 아무리 대용량 DB라도 B-Tree의 깊이가 4 ~ 5 이상까지 깊어지는 경우는 거의 발생하지는 않는다.