8.3 B-Tree 인덱스(1)

B-Tree 인덱스

B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되는 알고리즘이다.
B-Tree에는 여러가지 변형된 형태의 알고리즘이 있는데, B+-Tree또는 B*-Tree가 사용된다.
B는 Binary(이진)의 약자가 아니라 Balanced를 의미한다.
B-Tree는 인덱스를 항상 정렬된 상태로 유지한다.

B-Tree 특성

B-Tree는 트리 구조의 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어 있다.
트리 구조의 가장 하위에 있는 노드를 리프 노드라고 하고, 중간의 노드를 브랜치 노드라고 한다.
데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.

특성

• 노드에는 2개 이상의 데이터(key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.
  
• 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B트리 라고 한다.
  
• 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 k+1개 여야 한다.
  
• 특정 노드의 왼쪽 서브 트리는 key보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성된다.
  
• 모든 리프 노드 들이 같은 레벨에 존재한다. - 즉 루트 노드에서 모든 리프 노드로 가는 경로의 길이가 같다.
  

B-Tree 탐색 과정

B-Tree는 루트 노드에서 탐색을 시작하여 하향식으로 탐색을 진행한다.
찾고자하는 값이 K라면?

1. 루트 노드에서 탐색 시작
2. K를 찾았다면 탐색 종료
3. K와 노드의 key값을 비교해 알맞은 자식 노드로 내려감.
4. 해당 과정을 리프 노드에 도달할 때까지 반복

InnoDB의 B-Tree 구조 및 특성

인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 정렬되지 않고 임의의 순서로 저장돼 있다.

데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것이 아니다.   
레코드가 삭제되어 빈 공간이 생긴다면, 
그 다음의 INSERT는 삭제된 공간을 재활용하도록 DBMS가 설계되 있기 때문에 
항상 INSERT된 순서로 저장되는 것은 아니다.

인덱스는 테이블의 키 컬럼만 가지고 있으므로, 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야한다.
이를 위해 인덱스의 리프 노드는 (인덱스 키, PK) 쌍으로 저장되어 있다.

클러스터드 인덱스, 인덱스 차이

PK가 아닌 인덱스로 조회하는 경우, 데이터를 따라 리프노드에 도달하면, 인덱스 키에 해당하는 레코드의 PK값이 저장되어 있다.
따라서, 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 PK를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.
(자세한 내용은 8.8절 클러스터링 인덱스에서..)

B-Tree 인덱스 키 추가 및 삭제

테이블의 레코드를 저장하거나 변경하는 경우 인덱스 키 추가나 삭제 작업이 발생한다.

인덱스 키 추가

B-tree에 새로운 키를 추가하기 위해서는 저장될 위치를 결정한 다음,
레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 인덱스에 저장한다.
만약, 리프 노드가 꽉차면 해당 노드를 분리하는데, 이때 상위 브랜치 노드까지 처리 범위가 넓어져서 새로운 키를 추가하기 때문에 (부모로 승격하는 것) 해당 연산은 비용이 많이 드는 작업이다.

innoDB에서는 체인지 버퍼를 활용하여 인덱스 키를 추가하는 작업을 지연시킬 수 있지만,
PK, UK 같이 유니크 제약 조건이 걸려있을 경우 중복 체크를 해야 하기 때문에
즉시 B-Tree에 추가하거나 삭제하는 작업을 진행한다.

체인지 버퍼  

체인지 버퍼는 특정 데이터 페이지가 버퍼 풀에 없을 때 
세컨더리 인덱스 페이지에 대한 변경 사항을 캐시하는 데이터 구조 

인덱스 삽입/업데이트 시 디스크에 대한 랜덤 I/O 연산이 비용이 크기 때문에 
변경이 필요한 인덱스 페이지가 버퍼 풀에 있으면 바로 업데이트를 하고, 
디스크로부터 읽어와야한다면 인서트 버퍼에 저장했다가 
사용자에게 결과를 바로 반환하도록 최적화.

 

1. 사용자 쿼리 실행(INSERT)
2. 버퍼 풀에 변경 사항이 발생한 페이지(B-Tree의 리프노드)가 있다면, 즉시 변경 사항 반영.
3. 버퍼 풀에 페이지 없다면, 인서트 버퍼에 임시로 기록해두고 쿼리 실행 완료
4. 추후 인덱스 페이지를 읽을 때마다 인서트 버퍼에서 머지해야 하는 키 값을 확인한 다음 병헙

인덱스 키 삭제

삭제할 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마킹 처리를 진행
마킹된 공간은 방치할 수도 있고, 재활용할 수도 있는데 마킹 작업 역시 디스크 I/O 작업이 필요해서
비용이 크다. 마찬가지로 MySQL 5.5 이상부터는 인덱스 추가처럼 지연 처리가 가능하다.

인덱스 키 변경

인덱스 키 값은 해당 값에 따라 저장될 리프 노드의 위치가 결정되기 때문에, B-Tree의 키 값이 변경되면 인덱스의 키 값만 변경하는 것은 불가능.
그래서 키 값을 먼저 삭제한 뒤, 새로운 키 값을 추가.
변경 역시 지연처리 가능.

인덱스 키 검색

INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축하는 이유는 빠른 검색을 위해서다.
인델스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 트리를 탐색한다.
인덱스 트리 탐색은 SELECT에서만 사용하는 것이 아니라, UPDATE나 DELETE를 처리하기 위해 항상 해당 레코드를 먼저 검색해야 할 경우에도 사용된다.
B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다.
부등호 비교 조건에서도 인덱스를 활용할 수 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없다.(ex : LIKE '%key')

인덱스를 이용한 검색에서 중요한 사실은 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 B-Tree의 빠른 검색 기능을 사용할 수 없다.
따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없다


InnoDB 스토리지 엔진에서 인덱스는 더 특별한 의미가 있다.
InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다.
따라서 UPDATE나 DELETE문장이 실행될 때 테입르에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다.
InnoDB 스토리지 엔진에서는 그만큼 인덱스의 설계가 중요하고 많은 부분에 영향을 끼친다.

B-Tree 인덱스 사용에 영향을 미치는 요소

B-Tree 인덱스는 인덱스를 구성하는 칼람의 크기와 레코드의 건수, 유니크한 인덱스 키 값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향을 받는다.

인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다.
인덱스도 결국은 페이지 단위로 관리가 되며, 로트와 브랜치, 그리고 리프 노드를 구분한 기준이 바로 페이지 단위이다.
B-Tree는 자식 노드의 개수가 가변적인 구조로, 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다.
페이지 기본크기인 16KB라고 가정, 인덱스의 키가 16 바이트, 자식 노드 주소가 12 바이트라고 가정하면,
16 * 1024 / (16+12) = 585 개의 자식 노드를 가질 수 있는 B-Tree가 된다.
그러나 키 값의 크기가 두 배인 32 바이트로 늘어났다고 가정하면, 16 * 1024 = (32+12) = 372개의 인덱스키를 한 페이지에 저장할 수 있다.
SELECT 쿼리가 레코드 500개를 읽어야 한다면, 전자는 인덱스 페이지 한번으로 해결될 수 있지만, 후자라면 2번 이상 디스크로부터 읽어야 한다.
결국 인덱스를 구성하는 키 값의 크기가 커진다면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다.
또한 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미한다.
하지만 인덱스를 캐싱해두는 버퍼 풀은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스의 크기가 커진다면, 메모리에 캐시해 둘 수 있는 레코드 수는 줄어든다.

B-Tree의 깊이

인덱스 키 값의 평균 크기가 늘어나면, 하나의 인덱스 페이지에 담을 수 있는 인덱스 키 값의 개수가 적어지고,
같은 레코드 건수라 하더라도 B-Tree의 깊이가 깊어져, 디스크 읽기가 더 많이 필요하다.
인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋다.

선택도(Selectivity), 기수성(Cardinality)

선택도 또는 카디널러티는 거의 같은 의미로 사용되며, 모든 인덱스 키값 가운데 유니크한 값의 수를 의미한다.
전체 인덱스의 키는 100개인데, 그 중 유니크한 키가 10개라면 카디널러티는 10이다.
인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 카디널러티는 낮아지고 선택도 또한 떨어진다.
인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

CREATE TABLE tb_city (
country VARCHAR(10),   
city VARCHAR(10),   
INDEX ix_country (country) 
);

tb_City테이블은 1만건의 레코드를 가지고 있고, country칼람에만 인덱스가 준비되어 있다.

mysql> SELECT *         
	   FROM tb_test       
       WHERE country='KOREA' 
       AND city='SEOUL';

• country 칼람의 유니크 값이 10개일 때
  tb_city 테이블에는 10개의 국가(country)와 도시 정보가 저장돼 있는것이다.
  country='KOREA'라는 조건으로 검색하면 1000건이 일치하리라는 것을 예상할 수 있다.
  그런데 인덱스를 통해 검색된 1000건 중 city='SEOUL'인 레코드는 1건이므로 999건은 불필요하게 읽은 것이다.
• country 칼람의 유니크 값이 1000개일 때
  tb_city 테이블에는 1000개의 국가와 도시 정보가 저장돼 있는 것이다.
  이 케이스에서는 country='KOREA'라는 조건으로 검색하면 10건이 일치할 것이고,
  10건중 9건만 불필요하게 읽게되는 것이다.

이처럼 인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미친다.

읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다.
레코드가 100만건이 저장돼 있는데, 그중에서 50만 건을 읽어야 하는 쿼리가 있을 때,
전체 테이블을 모두 읽어서 필요없는 50만건을 버리는 것이 효율적일지, 인덱스를 통해 필요한 50만 건만 읽어오는 것이 효율적일지 판단해야 한다.
인덱스를 이용한 읽기의 손익 분기점이 얼마인지 판단할 필요가 있는데,
일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4 ~ 5배 정도 비용이 더 많이 드는 작업이라고 예측한다.
즉, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블의 20 ~ 25%를 넘어서면 인덱스를 이용하지 않고 모두 직접 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다.


전체 100만건의 레코드 가운데 50만건을 읽어야 하는 작업은 손익 분기점이 20~25%를 훨씬 넘어서기 때문에 옵티마이저는
인덱스를 이용하지 않고 풀 스캔으로 처리할 것이다.
때문에 강제로 인덱스를 사용하도록 힌트를 추가해도 성능상 얻는 이점이 별로 없다.