[DB / MySQL] Index의 동작 원리

인덱스

• 데이터베이스 개체(테이블, 인덱스, 뷰, 스토어드 프로시저, 트리거) 중 하나
• 데이터를 조회할 때 결과를 빠르게 찾는 데 쓰인다.
• 인덱스 없이 특정 데이터를 검색할 경우, 테이블 전체를 검사해야 한다.

-- customer 테이블의 customer_name 열에 인덱스를 지정
CREATE INDEX idx_customer_name ON customer(customer_name);

-- 인덱스를 통해 결과를 찾음
SELECT * FROM customer WHERE customer_name = "Kim";

 

인덱스의 동작 원리

* MySQL Database의 B-Tree 구조를 기준으로 설명

Index

• Clustered Index :
  MySQL이 자동으로 설정하는 index
  최대 효율을 위해 중복이 최대한 발생하지 않는 컬럼을 사용한다.
  
  1. 해당 테이블에 Auto increments값으로 PK가 있다면 해당 컬럼이 Clustered Index가 된다.
  2. 만약 PK가 없다면 Unique 컬럼을 Clustered Index로 설정한다.
  3. Unique 컬럼이 없다면 MySQL 내부적으로 Hidden Clustered Index Key (row ID)를 만들어 Clustered Index로 사용한다.
• Non Clustered Index :
  개발자 또는 DBA 등이 설정하는 모든 index
  멀티 컬럼 index의 경우 최대 16개의 컬럼을 사용할 수 있다.
  테이블당 index의 개수는 최대 64개까지 지정 가능하다. (Clustered Index까지 총 65개)
  
  

B-Tree Node

• MySQL에서는 Index 저장 구조로 B-Tree를 사용한다.
  
• 각 사각형 한 개를 Node 혹은 Page라고 부른다.
• MySQL에서는 Page 사이즈가 16KB로 설정되어있다.
• 최상단 노드를 root node, 최하단에 디스크 주소를 가지고 있는 노드를 leaf node, 둘 사이에 있는 노드를 branch node라고 한다.
• -- age 칼럼이 index로 설정되어있음 SELECT name FROM table WHERE age = 22;
• 위 쿼리에서 index를 통해 데이터를 어떻게 조회해올까?
  1. root node로 가서 age = 22인 값의 leaf노드로 가기 위한 경로를 안내받는다.
  2. root node는 branch node의 경로를 안내해주고,  branch node는 또 아래의 branch node 혹은 leaf node의 경로를 알려준다.
  3. leaf node까지 도착하면 leaf node는 index값과 디스크 주소값을 가지고 있다.
  4. 디스크에 접근해 '철수'를 조회한다.
• name을 조회했으므로 디스크까지 접근해야 한다.  (디스크 I/O 발생)
• 그러나 age를 조회했다면 디스크까지 접근할 필요 없이 B-Tree에서 바로 age가 22임을 알 수 있다.
  

  

  데이터 양이 많아질 수록 full scan보다 index scan이 더 빠르다. 
• 특정 데이터 양 시점까지는 full scan이 오히려 더 빠르다.
• 그 이유는 index를 통한 검색은 B-Tree에서 leaf node까지 찾아 내려간 후 해당 데이터를 찾기 위해 디스크로 접근하기 때문이다. 
• full scan은 B-Tree를 찾아가는 과정 없이 디스크로 가서 바로 모든 데이터를 읽어온다.
  • 데이터 양이 많지 않거나, index가 효율적으로 설정되어있지 않은 경우 오히려 full scan이 더 빠르다.
  • index full scan이 실행되는 경우, index full scan의 데이터가 테이블의 모든 데이터 양과 비슷한 경우 table full scan이 더 빠를 수 있다.

 

 

 

참고 블로그 : https://kyungyeon.dev/posts/66