MySQL이 인덱스 구조로 B+ 트리를 선택하는 이유는 무엇입니까? (상해)-MySQL 튜토리얼-php.cn

MySQL에서는 Innodb와 MyIsam 모두 B+ 트리를 인덱스 구조로 사용합니다(여기에서는 해시와 같은 다른 인덱스는 고려되지 않습니다). 이 기사에서는 가장 일반적인 이진 검색 트리부터 시작하여 다양한 트리가 해결하는 문제와 직면하는 새로운 문제를 점차적으로 설명함으로써 MySQL이 B+ 트리를 인덱스 구조로 선택하는 이유를 설명합니다.

MySQL이 인덱스 구조로 B+ 트리를 선택하는 이유는 무엇입니까? (상해)

1. 이진 검색 트리(BST): 불균형

이진 정렬 트리라고도 불리는 이진 검색 트리(BST, Binary Search Tree)는 이진 트리를 기반으로 해야 합니다. 만족: 어떤 노드의 왼쪽 하위 트리에 있는 모든 노드의 값은 루트 노드의 값보다 크지 않으며, 어떤 노드의 오른쪽 하위 트리에 있는 모든 노드의 값은 루트 노드의 값보다 작지 않습니다. 루트 노드. 다음은 BST(사진 출처)입니다.

빠른 조회가 필요한 경우 BST에 데이터를 저장하는 것이 일반적인 선택입니다. 이때 쿼리 시간은 트리 높이에 따라 달라지고 평균 시간 복잡도는 O(lgn)이기 때문입니다. 그러나 BST는 아래 그림(사진 출처)과 같이 편향되어 불균형이 될 수 있습니다. 이때 BST는 연결 리스트로 퇴화되고, 시간 복잡도는 O(n)으로 퇴화됩니다.

이 문제를 해결하기 위해 균형 이진 트리가 도입되었습니다.

2. 균형 이진 트리(AVL): 회전에는 시간이 많이 걸립니다

AVL 트리는 엄격하게 균형 잡힌 이진 트리입니다. 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 간의 높이 차이는 1을 초과할 수 없습니다. ; AVL 트리 검색, 삽입 및 삭제는 평균과 최악의 경우 모두 O(lgn)입니다.

AVL에서 균형을 이루는 열쇠는 회전 작업에 있습니다. 삽입 및 삭제는 이진 트리의 균형을 파괴할 수 있으며, 하나 이상의 트리 회전을 통해 트리의 균형을 다시 맞춰야 합니다. 데이터를 삽입할 때 최대 한 번의 회전(단일 회전 또는 이중 회전)만 필요하지만 데이터가 삭제되면 트리가 불균형하게 됩니다. AVL은 삭제된 노드에서 경로에 있는 모든 노드의 균형을 유지해야 합니다. 루트 노드로의 회전 크기는 O(lgn)입니다.

시간이 많이 걸리는 회전으로 인해 AVL트리는 데이터 삭제 시 매우 비효율적입니다; 삭제 작업이 많은 경우 균형을 유지하는 데 드는 비용이 이점보다 높을 수 있으므로 AVL은 실제로 널리 사용되지 않습니다. .

3. 레드-블랙 트리: 나무가 너무 큽니다

AVL 트리에 비해 레드-블랙 트리는 엄격한 균형을 추구하지 않고 대략적인 균형을 추구합니다. 단지 뿌리에서 잎까지 가능한 가장 긴 경로를 보장할 뿐입니다. 경로는 가능한 최단 경로의 두 배를 넘지 않습니다. 구현 관점에서 볼 때 레드-블랙 트리의 가장 큰 특징은 각 노드가 두 가지 색상(빨간색 또는 검정색) 중 하나에 속하고 노드 색상 구분이 특정 규칙을 충족해야 한다는 것입니다(구체적인 규칙은 생략합니다). . 레드-블랙 트리의 예는 다음과 같습니다(사진 출처):

AVL 트리에 비해 레드-블랙 트리의 쿼리 효율성은 트리의 균형이 악화되고 높이가 낮아지기 때문입니다. 더 높습니다. 그러나 데이터를 삽입하거나 삭제할 때 기본 균형을 유지하려면 O(1)번의 회전과 색상 변경만 필요하므로 레드-블랙 트리의 삭제 효율성이 크게 향상되었습니다. . AVL이 필요하지 않습니다. 트리는 O(lgn) 회전을 수행합니다. 일반적으로 레드-블랙 트리의 통계적 성능은 AVL의 성능보다 높습니다.

따라서 실제 응용 분야에서는 AVL 트리가 비교적 드물게 사용되는 반면, 레드-블랙 트리는 매우 널리 사용됩니다. 예를 들어, Java의 TreeMap은 정렬된 키-값 쌍을 저장하기 위해 빨간색-검정 트리를 사용하고, Java8의 HashMap은 연결된 목록 + 빨간색-검정 트리를 사용하여 해시 충돌 문제를 해결합니다(충돌하는 노드가 적을 경우 연결된 목록을 사용합니다. 충돌하는 노드가 많을수록 레드 블랙 트리를 사용하세요).

데이터가 메모리에 있는 상황(예: 위에서 언급한 TreeMap 및 HashMap)의 경우 레드-블랙 트리의 성능이 매우 뛰어납니다. 하지만 데이터가 디스크(예: MySQL와 같은 데이터베이스)와 같은 보조 저장 장치에 있는 상황의 경우 레드-블랙 트리는 잘 자라지 않습니다. 왜냐하면 레드-블랙 트리는 여전히 너무 높이 자라기 때문입니다. 데이터가 디스크에 있을 때 디스크 IO는 가장 큰 성능 병목 현상이 되며, 설계 목표는 IO 수를 최소화하는 것입니다. 트리 높이가 높을수록 추가, 삭제, 수정에 필요한 IO 시간이 늘어납니다. 성능에 심각한 영향을 미칠 수 있는 검색.

4. B-트리: 디스크를 위해 태어났습니다

B트리는 B-트리라고도 합니다(여기서 -는 빼기 기호가 아님). 디스크와 같은 저장 장치 설계된 다중 방향 균형 검색 트리는 이진 트리와 비교하여 B 트리의 각 리프가 아닌 노드는 여러 하위 트리를 가질 수 있습니다. 따라서 총 노드 수가 동일할 때 B-트리의 높이는 AVL 트리 및 레드-블랙 트리(B-트리는 "난쟁이"임)보다 훨씬 작으며 디스크 수는 IO가 크게 감소합니다.

B-트리를 정의할 때 가장 중요한 개념은 순서입니다. m차 B-트리의 경우 다음 조건이 충족되어야 합니다.

각 노드에는 최대 m개의 하위 노드가 포함됩니다.
루트 노드에 하위 노드가 포함된 경우 루트 노드를 제외하고 각 비리프 노드에는 최소 2개의 하위 노드가 포함됩니다.
k개의 하위 노드가 있는 리프가 아닌 노드에는 k - 1개의 레코드가 포함됩니다.
모든 리프 노드는 동일한 레이어에 있습니다.

B-tree의 정의는 주로 자식 노드의 수와 리프가 아닌 노드의 레코드를 제한한다는 것을 알 수 있습니다.

아래 그림은 3차 B-트리의 예입니다. (그림 출처):

B-트리의 장점은 작은 나무 높이뿐만 아니라 접근 지역성의 원리를 활용한다는 것입니다. . 지역성 원리란 특정 데이터를 사용할 때 짧은 시간 내에 근처의 데이터가 사용될 확률이 높다는 것을 의미합니다. B-트리는 동일한 노드에 유사한 키를 가진 데이터를 저장합니다. 데이터 중 하나에 액세스하면 데이터베이스는 전체 노드를 캐시로 읽습니다. 인접한 데이터에 즉시 액세스하면 캐시에서 직접 읽을 수 있습니다. 디스크 IO가 필요하지 않습니다. 즉, B-트리의 캐시 적중률이 더 높습니다.

B-트리에는 B-트리 구조를 사용하는 mongodb의 인덱스와 같은 데이터베이스의 일부 응용 프로그램이 있습니다. 그러나 많은 데이터베이스 애플리케이션에서는 B-트리의 변형인 B+ 트리가 사용됩니다.

5. B+ 트리

B+ 트리는 다중 방향 균형 검색 트리이기도 합니다. B-트리와의 주요 차이점은 다음과 같습니다.

B의 모든 노드(리프 노드 및 비리프 노드 포함) -tree는 실제 데이터를 저장합니다. B+ 트리의 리프 노드만 실제 데이터를 저장하고 리프가 아닌 노드는 키만 저장합니다. MySQL에서 여기에 언급된 실제 데이터는 행의 모든 데이터(예: Innodb의 클러스터형 인덱스)일 수도 있고 단순히 행의 기본 키(예: Innodb의 보조 인덱스)이거나 행의 주소(예: MyIsam의 비클러스터형 인덱스 등).
B 트리의 A 레코드는 한 번만 나타나며 반복적으로 나타나지 않는 반면, B+ 트리의 키는 반복적으로 나타날 수 있습니다. 리프 노드에는 확실히 나타나거나 리프가 아닌 노드에는 반복적으로 나타날 수 있습니다.
B+ 트리의 리프 노드는 이중 연결 리스트를 통해 연결됩니다.
B-트리의 리프가 아닌 노드의 경우 레코드 수는 하위 노드 수보다 1 적지만 B+ 트리의 레코드 수는 하위 노드 수와 같습니다.

따라서 B+ 트리는 B 트리에 비해 다음과 같은 장점이 있습니다.

더 적은 IO 횟수: B+ 트리의 리프가 아닌 노드에는 실제 데이터가 아닌 키만 포함되므로 각각 저장된 레코드 수 노드에서 B의 수보다 훨씬 크므로(즉, m의 순서가 더 큼) B+ 트리의 높이가 낮고 액세스에 필요한 IO의 수가 더 적습니다. 또한, 각 노드는 더 많은 레코드를 저장하므로 액세스 지역성 원칙이 더 잘 활용되고 캐시 적중률이 더 높습니다.
은 범위 쿼리에 더 적합합니다. B-트리에서 범위 쿼리를 수행할 때 먼저 검색할 하한을 찾은 다음 상한까지 B-트리를 순서대로 탐색합니다. B+ 트리의 범위 쿼리가 검색되는 동안 연결된 목록을 순회하면 됩니다.
보다 안정적인 쿼리 효율성: B-트리의 쿼리 시간 복잡도는 1과 트리 높이(각각 루트 노드와 리프 노드에 해당) 사이인 반면, B+ 트리의 쿼리 복잡도는 1에서 안정적입니다. 모든 데이터가 리프 노드에 있기 때문에 트리 높이입니다.

B+ 트리에도 단점이 있습니다. 키가 반복적으로 나타나기 때문에 더 많은 공간을 차지합니다. 그러나 성능상의 장점에 비해 공간적 단점은 수용할 수 있는 경우가 많으므로 데이터베이스에서는 B 트리보다 B+ 트리가 더 널리 사용됩니다.

6. B+ 트리의 힘을 느껴보세요

앞서 언급했듯이 레드-블랙 트리나 다른 이진 트리에 비해 B-트리/B+ 트리의 가장 큰 장점은 트리 높이가 더 작다는 것입니다. 실제로 Innodb의 B+ 인덱스의 경우 트리 높이는 일반적으로 2~4레벨입니다. 구체적인 추정을 해보겠습니다.

트리의 높이는 순서에 따라 결정됩니다. 순서가 클수록 트리의 크기는 짧아지며, 순서의 크기는 각 노드가 저장할 수 있는 레코드 수에 따라 달라집니다. Innodb의 각 노드는 하나의 페이지(page)를 사용하며, 페이지 크기는 16KB이며, 그 중 메타데이터는 약 128바이트(파일 관리 헤더 정보, 페이지 헤더 정보 등 포함)만 차지하며 대부분의 공간은 데이터를 저장하는 데 사용됩니다. .

리프가 아닌 노드의 경우 레코드에는 인덱스 키와 다음 수준 노드에 대한 포인터만 포함됩니다. 각 비리프 노드 페이지가 1000개의 레코드를 저장한다고 가정하면 각 레코드는 약 16바이트를 차지합니다. 이 가정은 인덱스가 정수이거나 더 짧은 문자열인 경우에 적합합니다. 더 나아가, 인덱스 열의 길이가 너무 길어서는 안 된다는 제안을 자주 듣습니다. 이유는 다음과 같습니다. 인덱스 열이 너무 길고 각 노드에 너무 적은 레코드가 포함되어 있으면 트리가 너무 길어지고 인덱싱 효과가 발생합니다. 그리고 인덱스는 더 많은 공간을 낭비하게 됩니다.
리프 노드의 경우 레코드에는 인덱스의 키와 값이 포함됩니다(값은 행의 기본 키, 전체 데이터 행 등일 수 있습니다. 자세한 내용은 이전 기사를 참조하세요). , 데이터의 양이 더 많습니다. 여기서는 각 리프 노드 페이지가 100개의 레코드를 저장한다고 가정합니다. 실제로 인덱스가 클러스터형 인덱스인 경우 이 숫자는 100보다 작을 수 있고 인덱스가 보조 인덱스인 경우 이 숫자는 100보다 훨씬 클 수 있습니다. 실제 상황에 따라 추정됩니다).

3계층 B+ 트리의 경우 첫 번째 계층(루트 노드)에는 1페이지가 있고 1000개의 레코드를 저장할 수 있습니다. 두 번째 계층에는 1000페이지가 있으며 1000*1000개의 레코드를 저장할 수 있습니다. 세 번째 계층(리프 노드)에는 1000*1000페이지가 있고 각 페이지는 100개의 레코드를 저장할 수 있으므로 1000*1000*100개의 레코드, 즉 1억 개의 레코드를 저장할 수 있습니다. 이진 트리의 경우 1억 개의 레코드를 저장하려면 약 26개의 레이어가 필요합니다.

7. 요약

마지막으로 다양한 트리가 해결한 문제와 직면한 새로운 문제를 요약합니다.

1), 이진 검색 트리(BST): 정렬의 기본적인 문제는 해결하지만 균형이 보장되지 않아 연결 목록으로 변질될 수 있습니다.

2 ), AVL(Balance Binary Tree): 회전을 통해 균형 문제를 해결하지만 회전 작업 효율이 너무 낮습니다

3), Red-Black Tree: 엄격한 균형을 버리고 AVL 회전을 해결합니다. 빨간색 및 검정색 노드 도입 효율성이 낮은 문제이지만 디스크와 같은 시나리오에서는 여전히 트리가 너무 높고 IO 수가 너무 많습니다.

4), B-트리: 다음으로 해결; 이진 트리를 다중 경로 균형 탐색 트리로 변경 트리가 너무 커지는 문제

5), B+ 트리: B 트리를 기반으로 리프가 아닌 노드를 순수 인덱스로 변환합니다. 데이터를 저장하지 않는 노드는 트리의 높이를 더욱 줄입니다. 또한 Leaf 노드는 포인터를 사용하여 연결된 목록에 연결되어 범위 쿼리를 더욱 효율적으로 만듭니다.