Index, B-Tree

· 3분 읽기

데이터베이스 성능 최적화에서 인덱스는 가장 중요한 요소 중 하나다.

수백만 건의 데이터에서 특정 레코드를 찾을 때 인덱스가 없다면 전체 테이블을 순회해야 하지만, 적절한 인덱스가 있다면 몇 번의 디스크 I/O만으로 원하는 데이터를 찾을 수 있다.

What’s Index?

인덱스(Index)는 데이터 조회 성능을 향상시키기 위한 자료구조이다. 책의 색인(Index)처럼 데이터베이스에서도 특정 값을 빠르게 찾을 수 있도록 돕는다.

당연히 무조건 좋기만 할 수는 없고 트레이드오프가 있다.

  1. 저장공간: 인덱스 자체가 추가 저장 공간을 차지한다.

  2. 쓰기 성능 저하: INSERT, UPDATE, DELETE 시 인덱스도 함께 갱신해야 한다.

  3. 메모리 사용: 인덱스를 메모리에 캐싱하면 추가 메모리가 필요하다.

따라서 인덱스를 아무렇게나 생성하면 안되고, 조회가 빈번한 컬럼에 선택적으로 생성하는게 유리하다는 것을 알 수 있다.

B-Tree?

B-Tree(Balanced Tree)는 1970년대에 디스크 기반 저장 시스템을 위해 설계된 자료구조라고 한다.

이진 트리(Binary Tree)와 달리 각 노드가 여러 개의 키와 자식을 가질 수 있다.

B-Tree 의 특성은 다음과 같다.

차수(order) 가 m 인 B-Tree:

  1. 각 노드는 최대 m 개의 자식을 가질 수 있다.

  2. 루트를 제외한 각 내부 노드는 최소 m/2 개의 자식을 가진다.

  3. 루트는 리프 노드가 아니라면 최소 2개의 자식을 가진다.

  4. k개의 자식을 가진 노드는 k-1 개의 키를 포함한다.

  5. 모든 리프 노드는 같은 깊이에 위치한다 (균형 트리)

![MySQL] B-tree, B+tree란? (인덱스와 연관지어서)](https://blog.kakaocdn.net/dna/cikell/btqBRvDU1xF/AAAAAAAAAAAAAAAAAAAAAH3xI6_zOaS5PATO6whDKWZ_N3ZPdPbhMzTkO-7HoGHC/img.jpg?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1772290799&allow_ip=&allow_referer=&signature=i05WBAqxQjXwwgsYW%2FDJTEWscio%3D )

위와 같은 트리가 있다고 가정해보자.

3을 찾는다고 하면:

  1. 루트 노드에서 3 < 30 이니까 왼쪽.

  2. 8보다도 작으니까 다시 왼쪽.

  3. 3 발견

디스크 기반 시스템에서 각 노드 접근은 디스크 I/O 를 의미한다. 따라서 트리의 높이가 낮을 수록 성능이 좋다.

B-Tree 는 각 노드가 많은 키를 저장해서 트리의 높이를 최소화한다.

B+Tree

실제 데이터베이스에서는 B-Tree 의 변형인 B+Tree 를 사용하고는 한다.

차이점

  • 데이터 저장 위치

    • B-Tree: 모든 노드에 데이터 저장

    • B+Tree: 리프 노드에만 데이터 저장, 내부 노드는 라우팅용 키만 저장

  • 리프 노드 연결

    • B-Tree: 연결 없음

    • B+Tree: Linked List 로 연결됨

  • 내부 노드 용량

    • B+Tree 는 내부 노드에 데이터를 저장하지 않으므로 더 많은 키를 저장 가능

    • 결과적으로 트리의 높이가 더 낮아진다.

B+Tree 를 사용하는 이유

  1. 범위 쿼리 효율성

시작 지점만 찾으면 리프 노드의 연결 리스트를 따라가면서 순차적으로 읽을 수 있다.

SELECT * FROM orders WHERE created_at BETWEEN 'YYYY-MM-DD' AND 'YYYY-MM-DD';
  1. 높은 fanout (더 얕은 트리)

내부 노드에 데이터를 저장하지 않으므로 더 많인 키를 저장할 수 있다.

  1. 일관된 성능

모든 조회가 리프 노드까지 내려가므로 성능이 예측 가능하다.