▲

GN⁺: B-트리와 데이터베이스 인덱스

 (planetscale.com)
41P by neo 3달전 | favorite | 댓글 1개

B-tree란 무엇인가?

  • B-tree는 많은 소프트웨어, 특히 데이터베이스 관리 시스템(DBMS)에서 기반이 되는 역할을 함

  • MySQL, Postgres, MongoDB, Dynamo 등은 인덱스를 통해 효율적인 데이터 조회를 수행하기 위해 B-tree에 의존함

  • B-tree와 B+tree가 어떻게 작동하는지, 왜 데이터베이스가 인덱스에 이를 사용하는지, UUID를 기본 키로 사용하는 것이 나쁜 생각일 수 있는 이유를 학습할 것임

  • B-tree는 _키_와 _값_으로 알려진 데이터 쌍을 컴퓨터 프로그래머가 트리와 유사한 구조라고 부르는 것에 저장함

  • B-tree는 노드(사각형)와 자식 포인터(노드를 연결하는 선)로 구성됨

  • 최상위 노드를 루트 노드, 맨 아래 수준의 노드를 리프 노드, 그 외 모든 노드를 내부 노드라고 부름

  • 아래는 B-tree의 정의임:

    • 각 노드는 N개의 키/값 쌍을 저장함(여기서 N은 1보다 크고 K 이하)
    • 각 내부 노드는 최소 N/2개의 키/값 쌍을 가짐(내부 노드는 리프나 루트가 아닌 노드)
    • 각 노드에는 N+1개의 자식이 있음
    • 루트 노드는 유일한 노드가 아닌 한 최소 하나의 값과 두 개의 자식을 가짐
    • 모든 리프는 동일한 수준에 있음

  • B-tree의 또 다른 핵심 특징은 정렬임. 각 노드 내에서 요소는 순서대로 유지됨

  • 이러한 정렬 기능으로 인해 매우 효율적으로 키를 검색할 수 있음. 검색은 루트 노드에서 시작하여:

    1. 검색하려는 키가 노드에 포함되어 있는지 확인
    2. 없다면, 추가하려는 경우 키가 삽입될 위치를 노드에서 찾음
    3. 이 지점에서 자식 포인터를 따라 다음 수준으로 이동하고 프로세스를 반복

  • 이런 식으로 검색할 때 하나의 키를 검색하기 위해 트리의 각 레벨에서 _하나_의 노드만 방문하면 됨

  • B-tree는 매우 많은 양의 데이터를 가지고 있으면서도 장기 저장(디스크)에 지속되어야 할 때 잘 작동하도록 특별히 고안되었음. 그 이유는 각 노드가 고정된 바이트 수를 사용하기 때문

  • B-tree에서 각 노드가 저장할 수 있는 값의 수는 각각에 할당된 바이트 수와 각 키/값 쌍에서 소비되는 바이트 수에 따라 다름

B+tree (데이터베이스에 최적화된)

  • B+tree는 B-tree와 유사하지만, 다음과 같은 규칙이 변경됨:
    • 키/값 쌍은 리프 노드에만 저장
    • 비리프 노드는 키와 연관된 자식 포인터만 저장
  • MySQL 인덱스에서 B+tree를 구현하는 방식에 특정한 두 가지 추가 규칙이 있음:
    • 비리프 노드는 N+1 대신 N개의 자식 포인터를 저장
    • 모든 노드에는 "다음" 및 "이전" 포인터도 포함되어 트리의 각 수준이 이중 연결 리스트 역할도 할 수 있음
  • B+tree가 데이터베이스에 더 적합한 이유는 두 가지:
    1. 내부 노드가 값을 저장할 필요가 없으므로 내부 노드당 더 많은 키를 넣을 수 있음. 이는 트리의 깊이를 줄이는 데 도움이 됨
    2. 모든 _값_은 같은 수준에 저장되고 하단 수준 연결 리스트를 통해 순서대로 순회할 수 있음

MySQL에서 B+tree 사용법

  • MySQL은 여러 스토리지 엔진을 지원하며, 가장 일반적으로 사용되는 엔진은 B+tree에 크게 의존하는 InnoDB임
  • 실제로 InnoDB는 테이블의 기본 키를 트리 키로 사용하여 _모든 테이블 데이터_를 B+tree에 저장할 정도로 크게 의존함
  • 새 InnoDB 테이블을 만들 때마다 기본 키를 지정해야 함
  • MySQL은 각각의 새 테이블에 대해 B+tree를 생성하고, 기본 키로 설정된 값이 트리의 키가 됨. 값은 각 행의 나머지 열 값이며 리프 노드에만 저장됨
  • 이러한 B+tree의 각 노드 크기는 기본적으로 16k로 설정됨
  • MySQL이 데이터 조각(키, 값 등)에 액세스해야 할 때마다, 다른 키나 값이 필요하지 않더라도 전체 연관된 페이지(B+tree 노드)를 디스크에서 로드함
  • InnoDB 테이블에 보조 인덱스를 생성하는 것도 일반적임. 각 보조 인덱스에 대해 추가 지속형 B+tree가 구성되며, 키는 사용자가 인덱스를 구축하기로 선택한 열이고 값은 연결된 행의 기본 키임

기본 키 선택: 삽입

  • 테이블 데이터가 B+tree에 배열되는 방식은 선택한 키에 따라 다르므로, PRIMARY KEY 선택이 테이블의 모든 데이터의 디스크 레이아웃에 영향을 미침
  • 기본 키로 일반적으로 선택하는 두 가지는:
    • 정수 시퀀스(BIGINT UNSIGNED AUTO_INCREMENT 등)
    • UUID (버전이 여러 개 있음)
  • UUIDv4 기본 키를 사용할 경우의 결과를 고려해 보면, 삽입 시:
    1. 삽입을 위해 방문된 노드는 미리 예측할 수 없음
    2. 삽입을 위한 대상 리프 노드를 예측할 수 없음
    3. 리프의 값은 정렬되지 않음
  • 많은 삽입 과정에서 트리의 많은 노드(페이지)를 방문해야 하므로 1번과 2번 문제가 발생. 이러한 과도한 읽기 및 쓰기는 성능 저하로 이어짐
  • BIGINT UNSIGNED AUTO_INCREMENT를 기본 키로 사용할 경우:
    1. 새 값 삽입 시 항상 가장 오른쪽 경로를 따름
    2. 리프는 트리의 오른쪽에만 추가됨
    3. 리프 수준에서 데이터는 삽입된 순서대로 정렬됨
  • 1번과 2번으로 인해 순차적으로 발생하는 많은 삽입은 동일한 페이지 경로를 다시 방문하므로 많은 키/값 쌍을 삽입할 때 I/O 요청이 줄어듦

기본 키 선택: 순서대로 데이터 읽기

  • 데이터베이스에서 시간 순서대로 데이터를 검색하는 것이 일반적임
  • UUIDv4를 기본 키로 사용할 경우, 검색 결과 값 시퀀스가 여러 비순차 리프 노드에 걸쳐 분산됨
  • 순차적으로 삽입된 값을 찾는 경우, 검색 결과가 포함된 모든 페이지가 서로 인접하게 됨. 여러 행을 검색할 때 모두 단일 페이지에서 서로 인접할 수도 있음
  • 이러한 쿼리 패턴의 경우 순차 기본 키를 사용하여 읽어야 하는 페이지 수를 줄일 수 있음

기본 키 선택: 크기

  • 기본 키 크기도 중요한 고려 사항임. 기본 키는 항상:
    1. 고갈되지 않을 만큼 충분히 커야 함
    2. 과도한 저장 공간을 사용하지 않을 만큼 작아야 함
  • 정수 시퀀스의 경우 더 작은 테이블에 MEDIUMINT(1600만 개 고유 값) 또는 INT(40억 개 고유 값)를 사용할 수 있음
  • 큰 테이블의 경우 BIGINT를 사용하여 안전하게 함(18억 경 가능한 값). BIGINT는 64비트(8바이트)임
  • UUID는 일반적으로 128비트(16바이트)로, MySQL의 가장 큰 정수 유형보다 두 배임
  • B+tree 노드는 고정 크기이므로 BIGINT를 사용하면 UUID보다 노드당 더 많은 키를 넣을 수 있음. 이는 더 얕은 트리와 더 빠른 조회로 이어짐

B+tree, 페이지 및 InnoDB

  • B+tree의 큰 장점 중 하나는 원하는 대로 노드 크기를 설정할 수 있다는 것
  • InnoDB에서 B+tree 노드는 일반적으로 InnoDB 페이지 크기인 16k로 설정됨
  • 쿼리 처리(따라서 B+tree 순회) 시 InnoDB는 디스크에서 개별 행과 열을 읽지 않음. 데이터 조각에 액세스해야 할 때마다 전체 연관 페이지를 디스크에서 로드함
  • InnoDB는 이를 완화하기 위해 몇 가지 기술이 있는데, 주요 기술은 버퍼 풀임. 버퍼 풀은 디스크의 페이지와 MySQL 쿼리 실행 사이에 있는 InnoDB 페이지용 메모리 내 캐시임
  • MySQL이 페이지를 읽어야 할 때 먼저 버퍼 풀에 이미 있는지 확인함. 있으면 거기서 읽어 디스크 I/O 작업을 건너뜀. 없으면 디스크에서 페이지를 찾아 버퍼 풀에 추가한 다음 쿼리 실행을 계속함
  • 버퍼 풀은 쿼리 성능을 엄청나게 향상시킴. 버퍼 풀이 없다면 쿼리 워크로드를 처리하기 위해 훨씬 더 많은 디스크 I/O 작업을 수행하게 됨

기타 상황

  • 여기서는 주로 순차 키와 임의/UUID 키 비교에 초점을 맞췄지만, 이러한 원칙은 고려 중인 기본 키나 보조 키의 종류에 관계없이 명심해야 할 유용한 사항임
  • 예를 들어 user.created_at 타임스탬프를 인덱스 키로 사용하는 것을 고려할 수도 있는데, 이는 순차 정수와 유사한 특성을 가짐. 레거시 데이터를 삽입하지 않는 한 삽입은 일반적으로 항상 가장 오른쪽 경로로 이동함
  • 반대로 user.email_address 문자열과 같은 것은 임의 키와 더 유사한 특성을 가짐. 사용자는 이메일 알파벳 순서대로 계정을 만들지 않으므로 삽입은 B+tree 전체에서 발생함

결론

  • B+트리, 인덱스, 기본 키 선택에 대해 많은 내용을 다룸
  • 겉으로 보기에는 간단해 보이지만 데이터베이스의 성능을 최대한 끌어올리려면 고려해야 할 미묘한 차이가 있음
  • 추가 실험을 위해 인터랙티브 B+트리 웹사이트를 방문해볼 것
▲
neo 3달전  [-]
Hacker News 의견

  • 위키를 B-Tree처럼 관리하는 전략을 사용하여 유용하게 유지함

    • 랜딩 페이지가 너무 많아지면 링크와 단락을 하위 페이지로 이동시킴
    • 유사하고 오래된 링크는 주제에 맞는 형제 페이지로 이동시킴
    • 최종적으로 오래된 문서는 랜딩 페이지에서 세 단계 아래로 이동됨
    • 문서화는 검색 문제로 귀결됨
    • 금요일 오후에 생산적으로 보내기 좋은 방법임

  • 오랫동안 이런 것을 찾고 있었음, 놀라운 게시물임

    • 복합 인덱스에 대한 섹션이 있었으면 좋겠음

  • 놀라운 시각 자료에 감사함

    • Aerospike 위에 BTree+ 인덱싱 지원 작업을 했음
    • 만료된 키를 BTree+에서 제거하는 것이 도전적이었음
    • 첫 번째 형제 리프 노드 내에서만 하나의 레벨 분기를 융합하기로 결정함
    • BTree+ 위에 샤딩을 추가하여 속도를 높이고 잠금 경쟁을 줄였음
    • 정리 과정에서 BTree+가 불균형해질 수 있음
    • 인덱스 재구축 기능을 제공하여 추가 정리 작업을 피함

  • Firefox 모바일에서 쿠키 모달이 작동하지 않음

    • 사용자에게 브라우저에서 설정할 수 있도록 해야 함

  • UUID 열을 기본 키로 사용하지 말아야 함

    • 128비트 int를 모든 관계 측면에 복사해야 함
    • 대부분의 경우 완전히 무작위임
    • 내부 테이블 관계에는 bigserial(64비트) PK를 사용하고, 애플리케이션 수준 식별자와 자연 키에는 UUID(128비트)를 사용해야 함
    • 데이터베이스가 매우 행복해질 것임

  • 훌륭한 교육 자료임

    • 이러한 인터랙티브 데모가 많은 도움이 됨

  • 디스크 블록과 B-트리 노드가 16k이고, 키, 값, 자식 포인터가 모두 8비트라면, 노드당 682개의 키/값과 683개의 자식 포인터를 저장할 수 있음

    • 세 레벨 트리는 3억 개 이상의 키/값 쌍을 저장할 수 있음
    • 각 요소당 8바이트여야 함

  • 훌륭한 기사임

    • InnoDB가 데이터를 B 트리 자체에 저장하는 것을 클러스터 인덱스라고 함
    • MyISAM은 비클러스터 인덱스였음
    • Oracle 등은 선택할 수 있게 함

  • 그래프에서 v0, v1, ...v10이 무엇을 의미하는지 물어봄

    • 다른 페이지를 의미하는지 궁금함

  • 아름다운 인터랙티브 시각화임

    • 교육과 대중화 측면에서 최고 수준임
답변달기