CS/Database

[Real MySQL] 8. 인덱스 - B-Tree, B+Tree, Hash 인덱스

olsohee 2024. 3. 18. 16:35

B-Tree 인덱스

B-Tree 인덱스에 대해 알기 전에 먼저 B-Tree 자료구조에 대해 알아보자. B-Tree는 자식을 2개만 갖는 이진 트리를 확장하여 N개의 자식을 갖는다. 그리고 좌우 자식 간의 균형이 맞지 않을 경우 비효율적이기 때문에 항상 균형을 맞춘다는 의미에서 균형 트리(Balanced Tree) 라고 한다. 즉, B-Tree의 B는 Binary(이진)의 약자가 아니라 Balanced(균형)의 약자이다.

 

B-Tree는 데이터베이스의 인덱싱 알고리즘 중 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. B-Tree는 칼럼의 원래 값을 변형시키지 않으며 항상 정렬된 상태로 유지한다. 전문 검색과 같은 특수한 요건이 아닌 경우 대부분의 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다.

페이지란?

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 기본 단위를 페이지 또는 블록이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 단위가 된다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다. 인덱스도 결국은 페이지 단위로 관리된다.

 

그래서 페이지에 저장되는 개별 데이터의 크기를 최대학 작게 하여, 1개의 페이지에 최대한 많은 데이터들을 저장하도록 하는 것이 중요하다. 페이지에 저장되는 데이터의 크기가 크면 다음과 같은 문제가 발생한다.

  • 디스크 I/O가 많아진다.
    • 레코드를 찾는데 1개의 페이지만으로 처리가 안되면 여러 개의 페이지를 읽어와야 한다. 따라서 추가 페이지를 읽는 디스크 I/O가 발생하기 때문에 성능이 떨어진다.
  • 메모리에 캐싱할 수 있는 페이지 수가 줄어든다.
    • 디스크 I/O를 통해 페이지를 읽어오면 버퍼 풀이라는 메모리에 데이터를 캐싱해둔다. 그런데 개별 데이터의 크기가 커지면 버퍼 풀에 캐싱할 수 있는 페이지 수가 줄어들게 된다. 

구조 및 특성

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

 

  • 인덱스는 인덱스 키로 사용된 칼럼만 갖고 있다. 딸서 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 하기 때문에 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다. 
  • 각 노드에는 페이지 단위로 저장된다.
  • 인덱스 키 값은 모두 정렬되어 있지만, 데이터 파일의 레코드는 정렬되어 있지 않다. 
    • 데이터 파일의 레코드가 INSERT된 순서대로 저장된다고 생각할 수 있지만 실제론 그렇지 않다. 레코드가 삭제되어 빈 공간이 생기면 그 다음의 INSERT는 가능한 삭제된 공간을 재활용하도록 DBMS가 설계되어 있기 때문에 항상 INSERT된 순서대로 저장되는 것은 아니다.
    • 반면 InnoDB에서는 레코드가 프라이머리 키 순서대로 정렬되어 저장된다. 즉, 대부분의 RDBMS의 데이터 파일에서 레코드는 임의의 순서로 저장되지만, InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 프라이머리 키 순서로 정렬되어 저장된다. 다른 DBMS에서는 클러스터링 기능이 선택 사항이지만, InnoDB에서는 사용자가 별도로 설정하지 않아도 디폴트로 클러스터링 테이블이 생성된다.

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

인덱스 키 추가

  • 새로운 인덱스 키가 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. 
    • MyISAM이나 MEMORY 스토리지 엔진: INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree에 저장한다.
    • InnoDB 스토리지 엔진: 이 작업을 좀 더 지능적으로 처리하는데, 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있다. 하지만 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가하거나 삭제한다.
  • 새로운 인덱스 키를 저장할 때 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 찾아야 한다. 그리고 저장 위치가 결정되면 레코드의 인덱스 키 값과 레코드의 주소를 B-Tree의 리프 노드에 저장한다.
  • 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리되어야 하는데, 이는 상위 브랜치 노드까지 처리 범위가 넓어진다. 이러한 작업 탓에 B-Tree는 상대적으로 새로운 키를 추가하는 쓰기 작업에 비용이 많이 든다. 

인덱스 키 삭제

  • 해당 키 값이 저장된 리프 노드를 찾아서 삭제 마킹을 한다.
  • 이때 삭제 마킹은 버퍼 풀에 있는 인덱스 구조에 먼저 적용된다.
    • 인덱스의 물리적 구조는 디스크 상에 위치하는데, 인덱스의 변경 사항은 먼저 메모리 내의 버퍼 풀에 반영된 후, 특정 조건(ex, 트랜잭션이 커밋될 때, 버퍼 풀이 가득 차서 디스크로 플러시될 때 등)에 디스크 내의 인덱스 구조에 반영된다. 
    • 즉, 삭제 마킹은 버퍼 풀에 있는 인덱스 구조의 캐시에 반영된다. 그리고 적절한 시점에 버퍼 풀의 내용이 디스크에 플러시될 때 시실제 디스크 내의 인덱스 구조에 삭제 마킹이 반영된다. 
  • 삭제 마킹이 이뤄지면, 삭제 표시만 이뤄질 뿐 디스크에서 즉각적으로 제거되지 않는다. 이렇게 함으로써 인덱스 구조의 잦은 재조정을 방지하고 성능을 유지할 수 있다. 삭제 마킹된 인덱스들은 필요할 때 백그라운드 프로세스에 의한 정리 작업에 의해 일괄적으로 제거된다.
  • 삭제 마킹된 공간은 그대로 방치하거나 재활용할 수 있다.

인덱스 키 변경

  • 인덱스의 키 값에 따라 인덱스 키가 저장될 B-Tree 리프 노드의 위치가 결정되므로, 인덱스 키 변경도 단순히 키 값만 변경되지 않는다.
  • 인덱스 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다. 그리고 이때 키 값의 삭제와 추가는 위에서 설명한 절차대로 처리된다.
  • 정리하자면, 인덱스 키 값을 변경하는 작업은 기존 인덱스 키 값을 삭제한 후 새로운 인덱스 키 값을 추가하는 작업으로 처리되고, InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업을 모두 체인지 버퍼를 활용해 지연 처리할 수 있다.

인덱스 키 검색

  • INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축하는 이유는 바로 빠른 검색을 위해서다.
  • 인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데, 이 과정을 "트리 탐색"이라 한다.
  • 인덱스 트리 탐색은 SELECT에서만 사용하는 것이 아니라 UPDATE나 DELETE 작업에서 레코드를 검색해야 하는 경우에도 사용된다.
  • B-Tree 인덱스를 이용한 검색은 100% 일치하거나 값의 앞부분만 일치하는 경우에 사용할 수 있다. 그리고 부등호 비교 조건에서도 인덱스를 활용할 수 있다. 그러나 인덱스를 구성하는 키 값 중 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없다. 

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

인덱스 키 값의 크기

  • 이진 트리의 경우, 각 노드가 2개의 자식만 가지므로 인덱스 검색이 상당히 비효율적이다. 그래서 B-Tree의 B가 Binary의 약자가 아닌 Balanced의 약자라는 것이다. 이진 트리와 다르게 B-Tree의 자식 노드의 개수는 가변적이다.
  • 그러면 MySQL의 B-Tree는 자식 노드를 몇 개까지 가질 수 있을까? 그것은 인덱스 페이지의 크기와 인덱스 키 값의 크기에 따라 결정된다.
  • InnoDB 스토리지 엔진의 페이지 크기는 4KB~64KB 사이의 값을 선택할 수 있지만 기본 값은 16KB이다. 인덱스의 키가 16바이트이고 자식 노드 주소가 12바이트라고 가정하면 다음과 같이 인덱스 페이지가 구성될 것이다. 

  • 그러면 인덱스 페이지 크기가 16KB라고 할 때 총 몇 개의 인덱스 키를 저장할 수 있을까? (1024 * 16) / (16 + 12) = 585개의 키를 저장할 수 있다. 즉 585개의 자식을 가질 수 있는 B-Tree가 되는 것이다.
  • 만약 인덱스 키 값이 커지면 어떻게 될까? 위 경우에서 키 값의 크기가 16바이트에서 32바이트로 늘었다고 가정하면, 한 인덱스 페이지에 (1024 * 16) / (32 + 12) = 372개의 인덱스 키를 저장할 수 있다. SELECT 쿼리가 레코드 500개를 읽어야 하는 경우에 전자는 인덱스 페이지 1개로 해결될 수 있었지만, 후자는 최소 2번 이상 디스크로부터 읽어야 한다.
  • 즉, 인덱스를 구성하는 키 값이 커지면 하나의 인덱스 페이지에 저장할 수 있는 인덱스의 개수가 줄어들며, 디스크로부터 읽어야 하는 횟수가 늘어나고(디스크 I/O 발생), 그만큼 느려진다는 것을 의미한다. 

B-Tree 깊이

  • 인덱스 키 값의 크기가 커질수록 하나의 인덱스 페이지에 담을 수 있는 인덱스 키 값의 개수가 적어지고, 따라서 같은 레코드 건수라고 하더라도 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.
  • 즉, 인덱스 키 값의 크기, 그리고 그로 인한 B-Tree의 깊이는 인덱스 조회 성능에 영향을 미친다.

선택도(기수성)

  • 인덱스에서 선택도(Selectivity) 또는 기수성(Cardinality)는 같은 의미로 사용되는데, 모든 인덱스 키 값 중에 유니크한 값의 개수를 의미한다.
  • 전체 인덱스 키 값은 100개인데, 그 중 유니크한 값이 10개라면 기수성은 10이다. 인덱스 키 값 중 중복된 값이 많아질수록 기수성이 낮아지고 동시에 선택도 또한 떨어진다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.
  • 예를 들어 tb_test 테이블의 전체 레코드 수가 1만 건이고, country  칼럼으로만 인덱스가 생성되었다고 가정하자. 이때 다음과 같은 쿼리를 실행했다고 가정하자. 참고로 country와 city가 중복된 경우는 없다고 가정하자. 
SELECT * FROM tb_test
WHERE country='KOREA' AND city='SEOUL';
  • country 칼럼의 유니크 값이 10개일 때
    • 즉 테이블에  10개의 country 정보가 저장되어 있는 것이다. 
    • MySQL 서버는 인덱스된 칼럼인 country에 대해 전체 레코드의 건수나 유니크한 값의 개수 등 통계 정보를 갖고 있다.
    • 따라서 이때 country='KOREA'라는 조건으로 인덱스를 검색하면 1,000개(10,000/10)의 레코드가 일치할 것이라고 예상한다.
    • 그러나 실제 인덱스를 통해 조회한 1,000건 가운데 city='SEOUL'인 레코드는 1건이므로 불필요한 999건을 조회한 것이다.
  • country 칼럼의 유니크 값이 1000개일 때
    • 이때 country='KOREA'라는 조건으로 인덱스를 검색하면 10개(10,000/1,000)의 레코드가 일치할 것이라고 예상한다.
    • 그러나 실제 인덱스를 통해 조회한 10건 가운데 city='SEOUL'인 레코드는 1건이므로 불필요한 9건을 조회한 것이다.
  • 위 두 케이스를 살펴보면, 똑같은 쿼리를 실행해 똑같은 1건의 결과를 받았지만, 두 쿼리가 처리되는 과정의 효율성은 다르다는 것을 알 수 있다.
  • Caridinality가 높은 칼럼에 인덱스를 거는 것이 좋다는 말의 의미가 이와 같다. 이처럼 인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미친다.

읽어야 하는 레코드의 건수

  • 테이블에 레코드가 100만 건이 저장돼 있는데, 그중에서 50만 건을 읽어야 하는 쿼리가 있다고 가정해 보자. 이 작업은 전체 테이블을 모두 읽어서 필요 없는 50만 건을 버리는 것이 효율적일지, 인덱스를 통해 필요한 50만 건만 읽어 오는 것이 효율적일지 판단해야 한다.
  • 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 1건 읽는 것보다 4~5배정도 비용이 더 많이 드는 작업인 것으로 예측한다. 따라서 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 직접 읽어서 필요한 레코드만 가려내는 필터링 방식으로 처리하는 것이 효율적이다.
  • 이때 전체 테이블 레코드의 20~25%를 넘는 데이터를 읽을 때는 강제로 인덱스를 사용하도록 힌트를 추가해도 성능상 얻을 수 있는 이점이 없기 때문에 MySQL의 옵티마이저가 힌트를 무시하고 테이블을 직접 읽는 방식으로 처리한다.

B-Tree 인덱스를 통한 데이터 읽기

인덱스 레인지 스캔

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용되는 방식이다. 예를 들어 다음과 같은 쿼리를 실행한다고 가정하자.

SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

 

  1. 위 그림에서도 알 수 있듯이 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어간다.
  2. 검색할 레코드의 시작점을 찾았으면 그때부터 리프 노드의 레코드만 순서대로 읽는다(스캔).
  3. 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다. 

위 그림은 인덱스만 읽는 경우를 보여준다. 하지만 B-Tree 인덱스의 리프 노드를 스캔하면서 실제 데이터 파일의 레코드를 읽어 와야 하는 경우도 많은데, 이 과정을 살펴보자. 

  1. 루트 노드와 브랜치 노드를 이용해 리프 노드의 스캔 시작 위치를 검색한다
  2. 리프 노드의 시작 지점부터 필요한 방향으로 인덱스를 읽는다(스캔). 이때 인덱스 키 값이 정렬되어 있기 때문에 어떤 방향으로 스캔하든지 순차적으로 스캔이 가능한 것이다.
  3. 리프 노드에서 검색 조건에 일치하는 건들은 실제 데이터 파일에서 레코드를 읽어오는 과정이 발생한다. 이때 레코드 한 건 한 건 단위로 랜덤 I/O 작업이 한 번씩 일어난다. 따라서 위 그림처럼 3건의 레코드가 검색 조건에 일치했다고 가정하면, 총 3번의 랜덤 I/O가 발생하는 것이다. 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업이다. 따라서 인덱스를 통해 읽어야 할 레코드가 전체 데이터 레코드의 20~25%를 넘으면 인덱스를 통하지 않고 테이블의 데이터를 직접 읽는 것이 더 효율적이다.

정리하자면 인덱스 레인지 스캔은 다음과 같은 3단계를 거친다.

  1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. (인덱스 탐색)
  2. 1번에서 탐색된 위치를 시작으로 필요한 만큼 인덱스를 차례대로 쭉 읽는다. (인덱스 스캔)
  3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 통해 실제 레코드가 저장된 페이지를 가져와서 최종 레코드를 읽는다.

이때 실행되는 쿼리에 따라 3번 과정이 일어나지 않을 수도 있는데, 이를 커버링 인덱스라고 한다. 커버링 인덱스로 처리되는 쿼리는 디스크의 I/O 작업이 일어나지 않기 때문에 랜덤 읽기의 성능이 빨라진다. 

인덱스 풀 스캔

인덱스 풀 스캔은 인덱스 기준으로 검색하지만 인덱스의 처음부터 끝까지 모두 읽는 방식을 의미한다. 대표적으로 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다. 예를 들어, 인덱스는 (A, B, C) 칼럼의 순서로 만들어져 있지만 쿼리의 조건절은 B칼럼이나 C칼럼으로 검색하는 경우이다. 인덱스 풀 스캔은 인덱스를 사용하기는 하지만 효율적인 방식은 아니다. 

루스 인덱스 스캔

루스 인덱스 스캔은 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다. 루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 동작하지만 중간에 필요하지 않은 인덱스 키 값은 무시하는 형태로 동작한다. 이는 일반적으로 GROUP BY 또는 MAX(), MIN() 함수에 대해 최적화하기 위해 사용된다.

 

다음과 같은 쿼리를 실행한다고 가정하자.

SELECT dept_no, MIN(emp_no) FROM dept_emp
WHERE dept_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no

 

위 쿼리에서 사용된 dept_emp 테이블은 다음과 같이 dept_no와 emp_no라는 두 개의 칼럼으로 인덱스가 생성되어 있다. 그리고 (dept_no, emp_no) 조합으로 인덱스가 정렬되어 있다.

이때 쿼리는 dept_no와 MIN(emp_no) 값을 조회해 오는 쿼리이다. 따라서 WHERE 조건을 만족하는 범위 전체를 다 스캔할 필요가 없으므로, 최적화를 위해 루스 인덱스 스캔이 사용된다. 위 그림을 보면 루스 인덱스 스캔을 사용함으로써 불필요한 부분은 무시하고 다음을 스캔하는 것을 알 수 있다.

인덱스 스킵 스캔

인덱스의 핵심은 값이 정렬되어 있다는 것이고, 이로 인해 인덱스를 구성하는 칼럼의 순서가 매우 중요하다. 예를 들어 employees 테이블에 다음과 같은 인덱스를 생성한다고 가정해보자.

ALTER TABLE employees
ADD INDEX ix_gender_birthday (gender, birth_date);

 

그리고 다음과 같은 쿼리를 실행한다고 가정하자.

// 1. 인덱스를 사용하지 못하는 쿼리
SELECT gender, birth_date FROM employees WHERE birth_date>='1965-02-01';

// 2. 인덱스를 사용할 수 있는 쿼리
SELECT gender, birth_date FROM employees WHERE gender='M' AND birth_date>='1965-02-01';

 

위 두 쿼리 중 gender와 birth_date를 조건으로 가진 2번 쿼리는 효율적으로 인덱스를 사용할 수 있지만, 1번 쿼리는 birth_date 칼럼부터 시작하는 인덱스가 없기 때문에 효율적인 인덱스 사용이 불가하다.

 

이런 경우, MySQL 8.0 이전에는 birth_date 칼럼부터 시작하는 인덱스를 새로 생성해야만 했다. 만약 birth_date 칼럼부터 시작하는 인덱스가 없는 상태로 쿼리를 실행할 경우, 풀 인덱스 스캔을 통해 비효율적인 인덱스 사용이 발생하거나, 테이블 풀 스캔이 일어날 것이다.

 

그러나 MySQL 8.0 버전부터는 옵티마이저가 gender 칼럼을 건너뛰어서 birth_date 칼럼만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입됐다. MySQL 옵티마이저는 우선 gender 칼럼에서 유니크한 값을 모두 조회해서 주어진 쿼리에 gender 칼럼의 조건을 추가해서 쿼리를 다시 실행하는 형태로 처리한다. gender 칼럼이 'M'과 'F' 두 개의 값만 가진다고 했을 때, 옵티마이저는 다음과 같은 쿼리를 실행하는 것과 유사하게 최적화를 한다.

SELECT gender, birth_date FROM employees WHERE gender='M' AND birth_date>='1965-02-01';
SELECT gender, birth_date FROM employees WHERE gender='F' AND birth_date>='1965-02-01';

그러나 인덱스 스킵 스캔은 다음과 같은 단점을 지닌다.

  • WHERE 조건절에 조건이 없는 인덱스의 선행 칼럼의 유니크한 값의 개수가 적어야 한다. 만약 유니크한 값의 개수가 매우 많다면 인덱스에서 스캔할 시작점을 검색하는 작업이 많이 필요해진다.
  • 쿼리가 인덱스에 존재하는 칼럼만으로 처리가 가능해야 한다(커버링 인덱스). 그렇지 않다면 인덱스 스킵 스캔이 아닌 풀 테이블 스캔이 실행된다.

다중 칼럼 인덱스

두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스라고 한다. 이때 주의할 점은 인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬돼 있다는 것이다. 따라서 다중 칼럼 인덱스에서는 인덱스 내 칼럼의 위치(순서)가 상당히 중요하다.

B+Tree 인덱스

B+Tree는 B-Tree의 확장 개념으로, B-Tree의 경우 브랜치 노드에 키와 데이터를 담을 수 있다. 하지만 B+Tree의 경우 브랜치 노드에 키만 담는다. 그리고 키를 통해 리프 노드를 찾아가면, 리프 노드에 키와 데이터가 저장되어 있다. 그리고 리프 노드 간에는 LinkedList로 연결되어 있다.

 

B+Tree의 장점은 다음과 같다.

  • 리프 노드를 제외하고 루트 노드와 브랜치 노드에 데이터를 담지 않기 때문에 메모리를 더 확보할 수 있고, 더 많은 키들을 수용할 수 있다. 
  • 하나의 노드에 더 많은 키들을 담을 수 있으므로 전체적인 트리의 높이가 낮아진다.
  • 풀 스캔시, B+Tree는 리프 노드에 데이터가 모두 있으며 이들이 LinkedList로 연결되어 있기 때문에 리프 노드만 한 번 선형탐색하면 된다. 반면 B-Tree는 트리 전체의 모든 노드를 확인해야 한다.

B-Tree VS B+Tree

  B-Tree B+Tree
데이터 저장 브랜치 노드, 리프 노드 모두 데이터 저장 가능 리프 노드에만 데이터 저장 가능
트리의 높이 높음 낮음
검색 속도 자주 검색되는 데이터를 루트 노드와 가까운 브랜치 노드에 저장할 수 있음. 루트 노드와 가까운 경우 데이터 검색이 빠름. 데이터가 리프 노드에만 존재하므로 리프 노드까지 가야 함. 즉, B-Tree와 다르게 best도 worst도 없음(무조건 O(logN)).
풀 스캔 시 검색 속도 모든 노드 탐색 리프 노드에서 선형 탐색
LinkedList 없음 리프 노드끼리 LinkedList로 연결됨

Hash 인덱스

Hash 인덱스는 해시 테이블 자료구조로 인덱스를 관리한다. 즉, 인덱스를 건 특정 컬럼 값에 해시 함수를 적용하여 해시 값을 얻고, 이 해시 값에 해당하는 위치에 인덱스를 건 컬럼 값과 해당 레코드가 저장된 위치 정보가 저장된다.

B-Tree에 비해 Hash 인덱스가 자주 사용되지 않는 이유는 무엇일까?

 

 Hash 기반의 인덱스는 각 컬럼 값들을 기준으로 정렬되어 있지 않다. 따라서 <와 같은 범위 조건 검색이나 ORDER BY와 같은 정렬 조건 검색에서 사용이 불가하다. 

B-Tree가 데이터베이스 인덱스로 주로 사용되는 이유

그렇다면 B-Tree가 데이터베이스의 인덱싱 알고리즘 중 가장 일반적으로 사용되는 이유는 무엇일까? 일반적인 트리는 데이터 조회시 O(logN)의 시간 복잡도를 갖는다. 

그러나 트리 노드 요소가 한 쪽으로 쏠리게 되면 O(N)의 시간 복잡도를 갖게 되어 리스트와 별반 다를 것이 없어진다.

따라서 인덱스에서 빠른 조회를 위해 밸런스 트리, 그 중 B-Tree를 사용하는 것이다.

밸런스 트리(Balanced Tree)

트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬되어 왼쪽과 오른쪽의 자식 노드 수를 유지하는 트리이다. 따라서 데이터 조회 시 O(logN)의 시간 복잡도를 보장한다. 밸런스 트리는 대표적으로 RedBlack-Tree와 B-Tree가 있다.

  • RedBlack-Tree: 각 노드는 하나의 데이터만 가진 상태이며, 좌우 자식 노드의 개수가 일치하는 밸런스 트리이다. 

  • B-Tree: RedBlack-Tree와 마찬가지로 밸런스 트리이다. 그러나 각 노드에 여러 데이터가 저장될 수 있고 이들은 정렬되어 있다. 

RedBlack-Tree가 아닌 B-Tree가 인덱스로 사용되는 이유

둘 다 밸런스 트리이며 데이터 조회 시 O(logN)의 시간 복잡도를 갖는다.

 

그러나 하나의 노드가 갖는 데이터 갯수가 다르다. RedBlack-Tree는 무조건 하나의 노드에 하나의 데이터만 갖지만, B-Tree는 하나의 노드에 여러 개의 데이터를 갖는다. 그리고 B-Tree의 각 노드는 배열 형태로 실제 물리적 메모리 공간에 연속되어 위치한다. 따라서 같은 노드 공간끼리는 포인터로 참조하는 것이 아닌, 실제 메모리에서 바로 다음 인덱스에 접근하는 것이다. 이러한 이유로 같은 노드 내에서의 데이터 탐색이 빠르다.

 

반면 RedBlack-Tree는 각 노드가 하나의 데이터만 갖게 되므로 데이터에 접근할 때 무조건 참조를 통해 접근해야 한다. 따라서 참조를 통한 접근에는 CPU 내부적으로 주소를 알아내기 위한 연산이 수행된다.

해시 테이블을 인덱스로 사용하지 않는 이유

인덱스는 빠른 검색을 위해 존재한다. 그렇다면 탐색 시간이 가장 빠른 해시 테이블을 인덱스로 사용하지 않는 이유는 무엇일까?

 

해시 테이블은 해시 함수를 통해 나온 해시 값을 이용하여 O(1)의 시간으로 데이터에 접근한다. (해시 충돌로 인해 최악의 경우 O(N)도 가능하지만 평균적으로는 O(1)이다.)

 

그러나 이는 오직 1개의 데이터를 탐색하는 시간이다. 우리는 DB에서 등호(=)뿐만 아니라 부등호(<, >)도 사용할 수 있다. 즉, 해시 테이블을 사용하면, 값들이 정렬되어 있지 않으므로 특정 값을 기준으로 크거나 작은 데이터들을 조회할 수 없다. 

 

즉, 기준 값과 같은 데이터 뿐만 아니라 크거나 작은 일정 범위의 데이터도 탐색할 수 있어야 하는 DB의 특성 상, 해시 테이블은 어울리지 않는 자료구조이다. 

배열을 인덱스로 사용하지 않는 이유

그렇다면 배열의 값들이 정렬된 상태라면 배열을 인덱스로 사용하는 것은 어떨까? 배열 또한 배열 인덱스를 통해 빠른 데이터 탐색이 가능하다. 하지만 탐색만 빠를 뿐, 배열은 데이터 삽입과 삭제의 성능이 매우 떨어진다. 배열의 중간에 데이터를 삽입하거나 삭제할 경우, 그 뒤의 값들의 위치를 한 칸씩 이동시켜야 하기 때문이다. 또한 데이터 수정의 경우에도 재정렬을 해줘야 한다. 

 

참고로 B-Tree는 데이터 삽입과 삭제의 경우, 트리의 높이만큼의 약 O(logN)의 시간 복잡도를 갖는다. 따라서 배열을 통해 O(N)의 시간이 걸리는 것에 비해 더 적은 시간이 걸린다.

LinkedList를 인덱스로 사용하지 않는 이유

배열이 데이터 삽입, 수정, 삭제가 느리다면 LinkedList를 사용하는 것을 고려할 수 있다. LikedList는 포인터 연결만 맺고 끊어주면 되기 때문이다. 그러나 LinkedList는 제일 앞 또는 뒤에서부터 데이터 탐색이 진행된다. 따라서 데이터 탐색에 오랜 시간이 걸릴 수 있다.

결론

결론적으로 데이터베이스 인덱스로 B-Tree가 가장 적합한 이유를 정리하면 다음과 같다.

  • 항상 정렬된 상태이므로, 특정 값을 기준으로 부등호 연산을 하거나 특정 범위를 탐색하기에 적합하다.
  • 하나의 노드 내에서 데이터 탐색을 할 때에는 참조 포인터 없이 물리적 메모리 주소에 접근이 가능하다. 즉, RedBlack-Treedㅔ 비해 참조 포인터를 사용하는 경우가 적어 데이터 접근 시 시간을 줄일 수 있다.
  • 데이터 삽입, 수정, 삭제의 경우에 최대 O(logN)의 시간 복잡도를 갖는다.

Reference

저작자표시

'CS > Database' 카테고리의 다른 글

[Real MySQL] 9. 옵티마이저와 힌트  (0) 2024.03.19
[Real MySQL] 8. 인덱스 - 디스크 읽기 방식, 인덱스  (1) 2024.03.18
SQL 알아보기  (0) 2024.03.14
데이터베이스 기본 개념  (0) 2024.03.06
관계형 데이터베이스(RDB) vs 비관계형 데이터베이스(NoSQL)  (0) 2024.03.04

'CS/Database'의 다른글

  • 현재글[Real MySQL] 8. 인덱스 - B-Tree, B+Tree, Hash 인덱스

관련글

티스토리툴바