# B-트리와 데이터베이스 인덱스 > Clean Markdown view of GeekNews topic #16702. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=16702](https://news.hada.io/topic?id=16702) - GeekNews Markdown: [https://news.hada.io/topic/16702.md](https://news.hada.io/topic/16702.md) - Type: GN+ - Author: [neo](https://news.hada.io/@neo) - Published: 2024-09-11T08:33:19+09:00 - Updated: 2024-09-11T08:33:19+09:00 - Original source: [planetscale.com](https://planetscale.com/blog/btrees-and-database-indexes) - Points: 41 - Comments: 1 ## Summary B-tree와 B+tree는 MySQL, Postgres, MongoDB 등 주요 데이터베이스 시스템에서 효율적인 데이터 조회를 위해 사용되며, 특히 B+tree는 내부 노드에 더 많은 키를 저장할 수 있어 데이터베이스에 최적화되어 있습니다. 원문에는 잘 만들어진 인터랙티브 그래픽이 포함되어 있으니 같이 보시기 바랍니다. ## Topic Body ### B-tree란 무엇인가? - B-tree는 많은 소프트웨어, 특히 데이터베이스 관리 시스템(DBMS)에서 기반이 되는 역할을 함 - MySQL, Postgres, MongoDB, Dynamo 등은 **인덱스**를 통해 효율적인 데이터 조회를 수행하기 위해 B-tree에 의존함 - B-tree와 B+tree가 어떻게 작동하는지, 왜 데이터베이스가 인덱스에 이를 사용하는지, UUID를 기본 키로 사용하는 것이 [나쁜 생각일 수 있는 이유](https://planetscale.com/blog/the-problem-with-using-a-uuid-primary-key-in-mysql)를 학습할 것임 - 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` (버전이 [여러 개](https://planetscale.com/blog/the-problem-with-using-a-uuid-primary-key-in-mysql) 있음) - 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+트리 웹사이트](https://bplustree.app/)를 방문해볼 것 ## Comments ### Comment 28798 - Author: neo - Created: 2024-09-11T08:33:20+09:00 - Points: 1 ###### [Hacker News 의견](https://news.ycombinator.com/item?id=41489832) - 위키를 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이 무엇을 의미하는지 물어봄 - 다른 페이지를 의미하는지 궁금함 - 아름다운 인터랙티브 시각화임 - 교육과 대중화 측면에서 최고 수준임