MySQL 인덱스에 따른 산술적 계산량 차이

MySQL 응용 프로그램을 개발한 개발자라면 빈번하게 요청되거나, 빠른 검색이 필요한 경우 인덱스(index) 지정이 필수라는걸 이미 알고 있을 것이다. 그 차이는 데이터 양이 많아질 수록 크게 차이가 나기 때문. 그렇다면 산술적으로 어느정도 차이가 있는걸까?

MySQL의 인덱스 구조를 이해하려면 MySQL 쿼리에 대한 ‘동작 구조’를 먼저 이해 해야 한다. 간단한 예제를 만들어보자. Facebook OAuth 를 통해 얻은 사용자 정보를 저장하는 users Table 과 포스트 정보를 갖고 오기 위한 posts Table 을 만들자.

CREATE TABLE facebook.users
  (id integer, 
   name varchar(250),
 );

CREATE TABLE facebook.posts
  (post_id integer,
   uid integer, 
   content varchar(250),
);

이 때 사용자 gloria의 ‘모든’ 포스트 정보를 얻으려면 posts Tabke에서 user.id를 키로 해당 레코드를 추출하면 된다. 이를 위한 쿼리는 다음과 같을 것이다.

SELECT content FROM posts WHERE uid =..  gloria의 user.id

이 쿼리를 실행했을 때 MySQL 의 동작은

1. posts테이블의 모든 레코드를 읽고
2. uid 필드를 조사해 user.id 의 문자열이 gloria 와 일치하는 레코드를 찾는다.

단순히 생각해도 posts 테이블의 레코드 수가 증가하면 이를 추출하기 위한 탐색 시간은 자연 증가하게 된다. 이 탐색의 계산량은 posts 테이블에 있는 레코드 수를 n 으로 할 경우 O(n)이 된다. (= 선형 탐색에서의 계산량)

인덱스를 지정한 경우

MySQL의 인덱스(index)는 효과적으로 제목을 찾기 위해 “색인” 작업 하는것을 의미한다. 사전에서 “데이터베이스”라는 단어를 찾을 때 첫 페이지 부터 이 단어를 찾는 사람은 없을 것이다. 일반적으로 “ㄷ”의 색인(혹은 목차)을 기준으로 “데” 시작 페이지로 이동할 것이고 이런 행위를 반복해 “데이터베이스” 설명이 있는 페이지를 찾을 것이다.

DB 에서도 마찮가지로 검색 시간을 효율적으로 하기 위한 “색인(index)” 을 붙인다. 앞서 만든 Facebook의 경우 사용자 정보를 정리한 테이블 users와 사용자의 포스트를 정리한 posts 테이블이 있고, 사용자 gloria의 posts를 posts Table에서 추출할 하려면 일반적인 쿼리를 실행, 모든 사용자의 posts 레코드에 비례한 탐색 시간이 필요하게 된다.  (앞서 언급한 O(n)의 복잡한 설명)

이 때 다음과 같이 posts Table의 uid를 인덱스로 지정하면 gloria의 user.id와 posts.uid가 일치하는 레코드만 ‘콕’ 찝어 검색할 수 있게 된다.

CREATE TABLE facebook.users
  (id integer, 
   name varchar(250),
 );

CREATE TABLE facebook.posts
  (post_id integer,
   uid integer, 
   conent varchar(250),
   INDEX (uid)
);

MySQL의 인덱스는 B-Tree 데이터 구조로 구현되어 있다. 따라서 gloria의 posts를 추출하는데 필요한 탐색 시간은 O(log n)이 된다.

인덱스 유무에 따른 계산량 차이

posts Table의 uid에 인덱스를 지정하지 않는 경우 계산량은 O(n), 인덱스를 지정한 경우 계산량은 O(log n)임을 이미 설명했다. 전자의 계산량은 레코드가 늘어날 수록 선형으로 증가해 효율이 떨어지는것을 알 수 있다. 시험삼아 구체적인 계산량을 산출해 보자. 레코드 수를 n 이라하고 이 값을 각각 1,024와 1,048,576으로 가정했을때의 각각의 계산량은 다음과 같다.

1. posts Table에 등록된 레코드 수 n=1,024 의 경우
   1. 인덱스가 없을 경우 : 1,024
   2. 인덱스가 있을 경우 : 10
2. posts Table에 등록된 레코드 수 n=1,048,576 의 경우
   1. 인덱스가 없을 경우 : 1,048,576
   2. 인덱스가 있을 경우 : 20

이처럼 레코드 수가 증가할 수록 인덱스 여부가 계산량에 큰 영향을 미친다는 것을 알 수 있다. B-tree 에 대한 글은 다음 블로그를 참고하기 바란다.

• https://12bme.tistory.com/138
• https://medium.com/@swknight13/dbms-%EC%9D%98-%EC%9D%B8%EB%8D%B1%EC%8A%A4-b-tree-4ff039dca22
• https://idea-sketch.tistory.com/43