B-Tree 인덱스 - (1)

  이번 글과 다음 글을 통해서 B-Tree 인덱스에 대해서 자세히 알아보자.

 

📙 1. 인덱스 개념

🧰 1. 책과 인덱스

  인덱스란 책의 맨 끝에 있는 찾아보기(= 색인)에 비유할 수 있다. '찾아보기'를 인덱스라고 한다면, '책의 내용'은 데이터 파일에 해당하고, '페이지 번호'는 데이터 파일에 저장된 레코드의 주소라고 할 수 있다.

 

  DBMS에서 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸린다. 그래서 칼럼(또는 칼럼들)의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍(key-value)으로 삼아 인덱스를 만들어 두는 것이다.

 

  책의 '찾아보기'와 DBMS의 인덱스의 중요한 공통점은 '정렬'이다. '찾아보기'는 'ㄱ, ㄴ, ㄷ, ㄹ,...'과 같은 순서로 정렬되어 있는데, DBMS의 인덱스도 마찬가지로 칼럼의 값을 주어진 순더로 미리 정렬해서 보관한다.

 

🧰 2. 자료구조와 인덱스

  프로그래밍 언어의 자료구조를 이용하면 인덱스와 데이터 파일의 특성을 이해해 보자. 필요한 자료 구조 지식은 아래와 같다.

  SortedList는 저장되는 값을 항상 정렬된 상태로 유지하는 자료 구조이며, ArrayList는 값을 저장되는 순서 그대로 유지하는 자료구조이다.

 

  SortedList는 DBMS의 인덱스와 같은 자료 구조이며, ArrayList는 데이터 파일과 같은 자료 구조를 사용한다.

  그래서 DBMS의 인덱스는 SortedList와 마찬가지로 저장되는 칼럼의 값을 이용해 항상 정렬된 상태를 유지한다. 데이터 파일은 ArrayList와 같이 저장된 순서대로 별도의 정렬 없이 그대로 저장해 둔다.

 

  DBMS에서 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다.

  그 이유는 SortedList 자료 구조는 데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아올 수 있기 때문이다.

  DBMS의 인덱스도 인덱스가 많은 테이블은 당연히 INSERT나 UPDATE, DELETE 문장의 처리가 느려진다. 하지만, 이미 정렬된 '찾아보기'용 표(인덱스)를 가지고 있기 때문에 SELECT 문장은 매우 빠르게 처리할 수 있다.

 

 

📙 2. B-Tree의 구조 및 특성

  B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. 아직까지 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다.

  B-Tree는 칼럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다. 전문 검색과 같은 특수한 요건이 아닌 경우, 대부분 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다.

  B-Tree는 트리 구조의 최상위에 하나의 '루트 노드(Root node)'가 존재하고 그 하위에 자식 노드가 붙어 있는 형태다. 트리 구조의 가장 하위에 있는 노드를 '리프 노드(Leaf node)'라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 '브랜치 노드(Branch node)'라고 한다.

  데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.

 

  인덱스의 개념을 설명하는 부분에서 살펴봤듯이 대부분 RDBMS의 데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임의의 순서로 저장된다. 하지만, InnoDB 테이블에서 레코드는 클러스터 되어 디스크에 저장되므로 기본적으로 PK 순서로 정렬되어 저장된다.

 

  위의 그림은 MyISAM 스토리지 엔진과 InnoDB 스토리지 엔진에서의 'B-Tree의 리프 노드와 테이블 데이터 레코드의 관계'를 보여준다.

  두 스토리지 엔진의 인덱스에서 가장 큰 차이점은 세컨더리 인덱스를 통해 데이터 파일의 레코드를 찾아가는 방법에 있다. MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가지는 반면 InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다고 볼 수 있다.

  그래서 InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 MyISAM을 이용한 것처럼 데이터 파일을 바로 찾아가지 못한다. InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 PK를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.

 

 

📙 3. B-Tree 인덱스 키 추가, 삭제, 변경, 검색

🧰 1. 인덱스 키 추가

  새로운 키 값이 B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다.

  리프 노드가 꽉 차서 더는 저장할 수 없을 대는 리프 노드가 분리(Split)되어야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 드는 것으로 알려졌다.

 

  테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다.

  MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스에 변경한다. 하지만, InnoDB 스토리지 엔진은 이 작업을 조금 더 지능적으로 처리하는데, 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있다.

  그러나 PK나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가하거나 삭제한다.

 

🧰 2. 인덱스 키 삭제

  B-Tree의 키 값이 삭제되는 경우는 상당히 간단하다.

  해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있다.

  InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링 되어 지연 처리될 수도 있다.

 

🧰 3. 인덱스 키 변경

  인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스상의 키 값만 변경하는 것은 불가능하다.

  B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다. InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리 될 수 있다.

 

🧰 4. 인덱스 키 검색

  인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행한다. 이 과정을 '트리 탐색'이라고 한다.

 

  B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있다. 부등호(<, >)비교 조건에서도 인덱스를 활용할 수 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없다.

  또한, 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다. 이미 변형된 값은 B-Tree 인덱스에 존재하는 값이 아니다.

  따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없으므로 주의해야 한다.

 

 

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

🧰 1. 인덱스 키 값의 크기

  InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다.

  또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링 하는 기본 단위이기도 하다. 인덱스도 결국은 페이지 단위로 관리되며, '루트 노드, 브랜치 노드, 리프 노드'를 구분한 기준이 바로 페이지 단위다.

 

  B-Tree의 자식 노드 개수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. InnoDB 스토리지 엔진의 페이지 크기의 값을 조절할 수 있지만 기본값은 16KB이다.

  페이지 크기의 기본값(16KB), 인덱스의 키(16바이트), 자식 노드 주소 영역(12바이트)이 있다고 하자. 그러면 하나의 인덱스 페이지에는 585개의 자식 노드를 가질 수 있다.

( 하나의 인덱스 페이지 / {(인덱스 키) + (자식 노드 주소 영역)} = 585 )

(16 x 1024 / (16 + 12) = 585)

 

  키 값의 크기가 커지게 되면 당연히 하나의 인덱스 페이지에 저장할 수 있는 자식 노드의 개수가 줄어든다. 결국 인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어햐 하는 횟수가 늘어나고, 그만큼 느려지게 된다.

 

  또한, 인덱스의 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미한다. 인덱스를 캐시해 두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에, 인덱스의 크기가 커지면 메모리에 캐시 해둘 수 있는 레코드 수가 줄어들고, 그렇게 되면 자연히 메모리의 효율이 떨어지게 된다.

 

🧰 2. B-Tree의 깊이

  B-Tree 인덱스의 깊이(Depth)는 상당히 중요하지만 직접 제어할 방법은 없다. 인덱스의 키 값의 크기가 커지면 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어진다. 그래서 같은 레코드 건수라 하더라도 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.

(하나의 페이지에 585개의 자식 노드를 가질 수 있는 경우, B-Tree의 깊이가 3이면 '585 x 585 x 585 = 최대 2억'개의 키 값을 가질 수 있다.

반면에, 하나의 페이지에 372개의 자식 노드를 가질 수 있는 경우, B-Tree의 깊이가 3이면 '372 x 372 x 372 = 최대 5천'개의 키 값만 가질 수 있다.)

 

🧰 3. 선택도(기수성)

  인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)은 거의 같은 의미로 사용되며, 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다. 전체 인덱스 키 값은 100인데, 그중에서 유니크한 값의 수가 10개라면 기수성은 10이다.

  인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지고 동시에 선택도 또한 떨어진다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

 

🧰 4. 읽어야 하는 레코드의 건수

  인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다. 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업인 것으로 예측한다.

  그래서 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는(필터링) 방식으로 처리하는 것이 효율적이다.

 

 

해당 글은 백은빈, 이성욱 님의 'Real MySQL 8.0'을 참고하였습니다.