Index - 2. B+Tree 인덱스

B+Tree Index

Leaf가 아닌 node들은 자식 node(page)에 대한 주소를 갖고 있고, Leaf node들은 실제 데이터 레코드가 어떤 페이지에 위치해 있는지의 주솟값을 가지고 있다.

• MyISAM - Primary Key Index와 Secondary Index 둘 다 ROWID(레코드의 실제 물리적 주솟값)를 포인터로 가진다.
• InnoDB - Primary Key Index가 ROWID 역할을 한다. Secondary Index는 데이터 레코드의 주솟값이 아닌, Primary Key를 포인터로 가진다. 따라서 Secondary Index를 통해 데이터를 검색할 때 DB는 Secondary Index → Primary Key Index → Data Record의 순서로 레코드를 찾아간다.

B+Tree Index에 영향을 미치는 요소

• Index Key 값의 크기 Index Key도 데이터의 하나이기 때문에 저장 공간을 차지한다. Index Key의 크기가 커지면 한 페이지에 저장할 수 있는 인덱스의 갯수가 적어진다. 따라서 모든 인덱스를 저장하기 위해 필요한 페이지의 갯수가 증가한다. 다수의 레코드를 가져오기 위해 읽어야 할 인덱스 페이지가 증가할 수 있어 성능이 감소할 수 있으며, 인덱스를 캐시해 두는 공간은 한정적이므로, Index Key의 크기가 커지는 만큼 캐싱할 수 있는 인덱스 수가 줄어들어 캐시 효율이 감소한다. ex) 페이지 하나의 크기가 16KB, Index Key에 해당하는 자식 노드 주소 크기를 12KB라고 한다면
  • Index Key의 크기가 16Byte일 때, 인덱스 하나의 크기는 16+12=28Byte이다. 페이지 하나에 들어가는 인덱스 갯수는, 16 * 1024 / 28 = 585개이다.
  • Index Key의 크기가 32Byte일 때, 인덱스 하나의 크기는 32+12=44Byte이다. 페이지 하나에 들어가는 인덱스 갯수는, 16*1024 / 44 = 372개이다.
• B+Tree Depth 레코드를 조회할 때 Tree의 node(page)를 몇 번이나 랜덤하게 읽어야 하는지와 관련된 요소이다. Depth는 직접적으로 제어할 수 없고, key의 크기에 따른 인덱스 페이지의 갯수가 간접적으로 depth에 영향을 미친다고 할 수 있다.
  
• 선택도(selectivity)/기수성(cardinality) Index Key중 Unique한 것, 다른 말로 하면 Distinct한 것이 몇 개나 되는가?
  • Key의 중복도가 높으면, 다시 말해 동일한 Key가 많아 Distinct한 것이 별로 없어 Selectivity가 낮으면, Index를 통해 조회할 때 다뤄야 할 대상이 많아져 성능이 느려진다. (ex. 성별)
  • Key의 중복도가 낮으면, 다시 말해 동일한 Key가 적어 Distinct한 것이 많아 Selectivity가 높으면, Index를 통해 조회할 때 다뤄야 할 대상이 적어져 빨리 처리할 수 있다. (ex. 주민번호)
• 읽어야 할 레코드의 개수 읽어야 할 레코드가 많다면, Table Full Scan을 통해 테이블의 전체 레코드를 가져온 뒤 필터링하여 조회하는 것이 Index를 통해 가져오는 것보다 효율적일 수 있다.
  

B+Tree Index를 이용한 데이터 읽기(MySQL 8.0 이상)

• Index Range Scan
  1. Root-Branch-Leaf 노드를 거쳐 조건을 만족하는 인덱스의 시작점 위치까지 찾아간다.
  2. 필요한 만큼 인덱스를 읽는다. B+Tree의 특성상 Leaf Node, 즉 페이지들은 Linked List로 연결되어 있기 때문에, 페이지의 끝에 도달했을 때 다음 페이지로 접근해 계속해서 읽는다.
  3. 읽어들인 인덱스를 이용해 레코드가 저장된 페이지에 접근하여 실제 레코드를 가져온다.
• Index Full Scan
  • 인덱스만을 통해 쿼리를 처리할 수 있을 때 사용한다.
  • 실제 데이터 레코드까지 읽어야 한다면 사용하지 않는다.
• Loose Index Scan
  • Index Range Scan과 비슷하지만, 중간에 필요 없는 Index Key 값은 Skip하고 넘어간다.
  • 인덱스는 항상 정렬되어 있다는 특징을 이용하기 때문에, GROUP BY나 MIN, MAX 등의 집합 함수 사용 시 효율적이다.
• Index Skip Scan
  • 결합 인덱스를 이용하는 경우 등에서, 조건절에 이용되는 조건 중 선행 칼럼 없이 후행 칼럼을 이용할 때 이용된다.
  • 내부적으로 DB에서 인덱스에 존재하는 선행 칼럼의 값들을 먼저 추출한 뒤, 이 추출한 선행 칼럼 값들을 이용하여 쿼리를 처리한다.
  • MySQL 8.0이상부터 지원하는 기능으로, 아직 제약 조건이 많다.
    1. 조건절에 조건이 없는 선행 칼럼의 Distinct한 값이 적어야 한다.
    2. 쿼리가 인덱스에 존재하는 값만으로 처리 가능해야 한다.

참고자료

• 백은빈, 이성욱, Real MySQL 8.0, 위키북스
• https://www.intel.co.kr/content/www/kr/ko/gaming/resources/ssd-v-hdd.html
• https://choicode.tistory.com/27