MySQL의 B-트리 인덱스와 B+-트리 인덱스의 차이점은 무엇입니까?

트리를 인덱스 데이터 구조로 사용하면 데이터를 검색할 때마다 트리의 한 노드, 즉 페이지가 디스크에서 읽혀집니다. 그러나 이진 트리의 각 노드는 하나의 데이터만 저장합니다. , 저장 공간을 한 페이지도 채울 수 없다면 추가 저장 공간이 낭비되지 않을까요? 이러한 이진 균형 탐색 트리의 단점을 해결하기 위해서는 단일 노드에 더 많은 데이터를 저장할 수 있는 데이터 구조, 즉 다방향 탐색 트리를 찾아야 한다.

1. 다중 방향 검색 트리

1. 완전한 이진 트리 높이: O(log2N), 여기서 2는 로그, 트리의 각 수준에 있는 노드 수입니다. . 완전한 M-way 검색 트리 높이: O(logmN), 여기서 M은 로그, 트리의 각 레이어에 있는 노드 수입니다. O(log2N)，其中2为对数，树每层的节点数；

2、完全M路搜索树的高度：O(logmN)，其中M为对数，树每层的节点数；

M路搜索树适用于存储数据量过大无法一次性加载到内存的场景。通过增加每层节点的个数和在每个节点存放更多的数据来在一层中存放更多的数据，从而降低树的高度，在数据查找时减少磁盘访问次数。

因此，如果每个节点包含的关键字数量和每层的节点数量增加，则树的高度将减少。尽管每个节点的数据确定会更加耗时，但B树的关注点在于解决磁盘性能瓶颈，因此单个节点搜索数据的成本可以被忽略。

2. B树-多路平衡搜索树

B树是一种M路搜索树，B树主要用于解决M路搜索树的不平衡导致树的高度变高，跟二叉树退化为链表导致性能问题一样。B树通过对每层的节点进行控制、调整，如节点分离，节点合并，一层满时向上分裂父节点来增加新的层等操作来来保证该M路搜索树的平衡。

在B树中，每个节点都是一个磁盘块（页），而阶数或者说路数M则规定了节点中最多的子节点数量。每个非叶子节点存放了关键字和指向儿子树的指针，具体数量为：M阶的B树，每个非叶子节点存放了M-1个关键字和M个指向子树的指针。如图为5阶B树结构的示意图：

3. B树索引

首先创建一张user表：

create table user(
	id int,
	name varchar,
	primary key(id)
) ROW_FORMAT=COMPACT;

假如我们使用B树对表中的用户记录建立索引：

B树的每个节点占用一个磁盘块，磁盘块也就是页，从上图可以看出，B树相对于平衡二叉树，每个节点存储了更多的主键key和数据data，并且每个节点拥有了更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会降低。假如我们要查找id=28的用户信息，那么查找流程如下：

1、根据根节点找到页1，读入内存。【磁盘I/O操作第1次】

2、比较键值28在区间（17,35），找到页1的指针p2；

3、根据p2指针找到页3，读入内存。【磁盘I/O操作第2次】

4、比较键值28在区间（26,35），找到页3的指针p2。

5、根据p2指针找到页8，读入内存。【磁盘I/O操作第3次】

6、在页8中的键值列表中找到键值28，键值对应的用户信息为(28,po)；

B-Tree相对于AVLTree

M-way 검색 트리는 시나리오에 적합합니다. 저장된 데이터의 양이 너무 커서 한 번에 메모리에 로드할 수 없는 경우. 레이어당 노드 수를 늘리고 각 노드에 더 많은 데이터를 저장하여 한 레이어에 더 많은 데이터를 저장함으로써 트리 높이를 줄이고 데이터 조회 중 디스크 액세스 횟수를 줄입니다.

그래서 각 노드에 포함된 키워드 수가 늘어나고 레벨당 노드 수가 증가하면 트리의 높이가 감소합니다. 각 노드의 데이터 결정에는 시간이 더 많이 걸리겠지만 B-트리는 디스크 성능 병목 현상을 해결하는 데 중점을 두므로 단일 노드에서 데이터를 검색하는 데 드는 비용은 무시할 수 있습니다.

2. B-트리 - 다중 방향 균형 탐색 트리

B-트리는 M-방향 탐색 트리의 불균형을 해결하는 데 주로 사용됩니다. 트리가 더 높아지고 이진 트리가 연결 목록으로 변질됩니다. 성능 문제는 동일합니다. B-트리는 노드 분리, 노드 병합, 한 레이어가 가득 차면 상위 노드를 위쪽으로 분할하여 새 레이어를 추가하는 등 각 레이어의 노드를 제어하고 조정하여 M-way 검색 트리의 균형을 보장합니다.

B-트리에서 각 노드는 디스크 블록(페이지)이며 순서 또는 경로 번호 M은 노드의 최대 하위 노드 수를 지정합니다. 각 비리프 노드는 하위 트리에 대한 키워드와 포인터를 저장합니다. 구체적인 숫자는 다음과 같습니다. M 순서 B-트리, 각 비리프 노드는 M-1 키워드와 하위 트리에 대한 M 포인터를 저장합니다. 그림은 5차 B-트리 구조의 개략도를 보여줍니다:

3. B-tree index

먼저 사용자 테이블을 생성합니다:

rrreeeB-tree를 사용하여 사용자 레코드를 인덱싱한다면 table:

B-트리의 각 노드는 디스크 블록을 차지하고 디스크 블록도 페이지입니다. 위 그림에서 알 수 있듯이 균형 이진 트리와 비교하면 B-트리의 각 노드는 -tree는 더 많은 기본 키와 데이터를 저장하며, 각 노드에는 자식 노드가 많을수록 일반적으로 자식 노드의 수를 순서라고 합니다. 위 그림의 B-트리는 3레벨 B-트리이며 높이는 다음과 같습니다. 또한 감소됩니다. id=28의 사용자 정보를 찾으려면 검색 과정은 다음과 같습니다.

1. 루트 노드에 따라 1페이지를 찾아서 메모리에 읽어옵니다. [디스크 I/O 작업 1차] 🎜🎜2. 간격(17,35)에서 키 값 28을 비교하고, 페이지 1의 포인터 p2를 찾습니다. 🎜🎜3. 기억 속으로 ​​말이죠. [디스크 I/O 작업 2차] 🎜🎜4. 간격(26,35)의 키 값 28을 비교하여 3페이지의 포인터 p2를 찾습니다. 🎜🎜5. p2 포인터에 따라 8페이지를 찾아 메모리에 읽어 들입니다. [디스크 I/O 작업 3번째] 🎜🎜6. 8페이지의 키 값 목록에서 키 값 28을 찾습니다. 키 값에 해당하는 사용자 정보는 (28,po)입니다. AVLTree에 비해 노드 수가 줄어들어 디스크 I/O를 사용할 때마다 메모리에서 가져온 데이터를 사용할 수 있어 쿼리 효율성이 향상됩니다. 🎜🎜4. B+Tree Index🎜🎜B+Tree는 B-Tree 기반의 최적화로, B+Tree의 속성: 🎜🎜1. 노드 키워드 수와 동일합니다. 🎜🎜3. 모든 키워드가 리프 노드에 표시되고 연결된 목록의 키워드가 순서대로 표시됩니다. 리프 노드는 리프 노드의 인덱스와 동일하며, 리프 노드는 (키워드) 데이터를 저장하는 데이터 계층과 동일합니다. 🎜🎜InnoDB 스토리지 엔진은 B+Tree를 사용하여 인덱스 구조를 구현합니다. 🎜🎜B-트리 구조 다이어그램을 보면, 각 노드에는 데이터의 키 값 외에 데이터 값도 포함되어 있음을 알 수 있습니다. 각 페이지의 저장 공간은 제한되어 있으며, 데이터 데이터가 크면 각 노드(즉, 한 페이지)에 저장할 수 있는 키의 수가 매우 적습니다. B - Tree의 깊이가 커져 쿼리 중 디스크 I/O 수가 증가하여 쿼리 효율성에 영향을 미칩니다. B+Tree에서는 모든 데이터 레코드 노드가 키 값 순서로 동일한 레이어의 리프 노드에 저장되며, 리프가 아닌 노드에는 키 값 정보만 저장되므로 각 노드에 저장되는 키 값의 수가 크게 늘어날 수 있습니다. node.B+Tree의 높이를 줄입니다. 🎜🎜🎜B+Tree는 B-Tree와 비교하여 몇 가지 차이점이 있습니다. 🎜🎜🎜1. 리프가 아닌 노드는 하위 노드 페이지 번호에 대한 키 값 정보만 저장합니다. 🎜🎜2. 포인터 🎜🎜3. 데이터 레코드는 리프 노드에 저장됩니다.

위 그림을 바탕으로 B+ 트리와 B-트리의 차이점을 살펴보겠습니다.

(2) B+ 트리에서는 리프가 아닌 노드가 키 값만 저장하는 반면 B-트리 노드는 키 값만 저장합니다. 키 값과 데이터 저장을 모두 저장합니다.

페이지 크기는 고정되어 있으며 InnoDB의 기본 페이지 크기는 16KB입니다. 데이터가 저장되지 않으면 더 많은 키 값이 저장되고 해당 트리의 순서가 커지며 결과적으로 데이터를 검색하는 데 필요한 디스크 IO 횟수가 늘어납니다. 다시 감소합니다. 데이터 쿼리 효율성도 빨라집니다.

또한 B+ 트리의 한 노드가 1000개의 키 값을 저장할 수 있다면 3계층 B+ 트리는 1000×1000×1000=10억 개의 데이터를 저장할 수 있습니다. 일반적으로 루트 노드는 메모리에 상주하므로(처음으로 루트 노드를 검색할 때 디스크를 읽을 필요가 없음) 일반적으로 10억 개의 데이터를 검색하는 데 2개의 디스크 IO만 필요합니다.

(2) B+ 트리 인덱스의 모든 데이터는 리프 노드에 저장되며 데이터가 순서대로 정렬됩니다.

B+ 트리의 페이지는 양방향 연결 목록으로 연결되고, 리프 노드의 데이터는 단방향 연결 목록으로 연결됩니다. 이렇게 하면 테이블의 모든 데이터를 찾을 수 있습니다. B+ 트리는 범위 쿼리, 정렬 쿼리, 그룹 쿼리 및 중복 제거 쿼리를 매우 간단하게 만듭니다. B-트리에서는 데이터가 여러 노드에 분산되어 있기 때문에 이를 구현하기가 쉽지 않습니다.

위 내용은 MySQL의 B-트리 인덱스와 B+-트리 인덱스의 차이점은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!