mysql 인덱스가 B+ 트리 구조를 사용하는 이유에 대해 심도 있게 이야기해보자.

이 글은 mysql에 대한 고급 연구입니다. mysql이 B+ 트리를 인덱스 데이터 구조로 사용하는 이유를 소개합니다. 모든 분들께 도움이 되길 바랍니다!

색인은 우리가 읽고 있는 책과 마찬가지로 특정 장으로 바로 넘어가고 싶을 때 페이지별로 목차만 보면 됩니다. 목차를 기준으로 페이지 번호를 찾으면 됩니다. [관련 권장사항: mysql 비디오 튜토리얼]

컴퓨터에는 이 디렉터리를 저장하기 위한 데이터 구조가 필요합니다. 일반적인 데이터 구조에는 해시 테이블, 이진 검색 트리, AVL(이진 균형 트리) 및 레드-블랙 트리가 포함됩니다. 그렇다면 Innodb와 MyISAM이 b+ 트리를 선택한 이유는 무엇입니까?

1. 해시 테이블

해시 테이블은 데이터의 위치를 ​​나타내는 첨자 0, 1, 2, 3...이 포함된 배열 + 연결 리스트입니다. 해시 테이블에 데이터를 저장하려면 먼저 데이터에 해시 알고리즘을 사용합니다(기본은 모듈로 연산입니다). 배열 길이가 13이면 모듈로 13 이후에는 0-12가 됩니다. 계산된 첨자가 동일하면 연결리스트는 첨자 위치를 따릅니다.

단점:

1. 해시 저장소를 사용하려면 모든 데이터 파일을 메모리에 추가해야 하므로 더 많은 메모리 공간을 소비합니다.
2. 해시 검색은 등가 쿼리로 매우 빠르지만, 각 데이터 사이에 범위 규칙이 없습니다. 그러나 실제 작업에서는 더 많은 범위 쿼리가 사용되므로 해시가 적합하지 않습니다.

mysql이 해시 테이블을 사용하지 않는다고 직접적으로 말할 수는 없지만 스토리지 엔진에 따라 결정되어야 합니다. 메모리 스토리지 엔진은 해시 테이블을 사용합니다

2. 이진 검색 트리

단점:

1. 그림과 같이 극단적인 경우 기울어짐 문제가 발생할 수 있으며, 결국 연결리스트 구조가 됩니다.
2. 트리 노드가 너무 깊어 검색의 IO가 증가하고 이제 IO가 검색의 병목 현상이 됩니다.

3. 이진 균형 트리-AVL

트리의 균형을 유지하고 피하기 위해 데이터 왜곡, 회전 연산이 필요하며, 왼쪽 또는 오른쪽 회전을 통해 가장 긴 하위 트리와 가장 짧은 하위 트리의 길이는 1을 초과할 수 없습니다. 1을 초과하면 엄밀한 의미의 AVL 트리가 아닙니다

단점:

1. 데이터의 양이 많을 경우 균형을 유지하기 위해 1-n 회전이 필요합니다. 이 회전은 삽입 및 삭제 효율성이 매우 낮고 쿼리 효율성이 매우 높습니다.

2. 가지 두 개만 있어도 데이터 양이 많을 때 트리의 깊이는 여전히 매우 깊습니다.

4. 레드-블랙 트리

가장 긴 하위 트리는 가장 짧은 하위 트리의 2배를 초과할 수 없습니다. 색상 변경과 회전을 통해 삽입과 쿼리가 균형을 이룹니다.

레드-블랙 트리는 Partial을 잃는 AVL 트리의 변형입니다. 삽입 성능을 향상시키기 위한 쿼리 성능. ㅋㅋㅋ 그리고 브랜치가 2개밖에 없어서 IO 수도 많습니다.

브랜치가 2개밖에 없고 깊이가 너무 깊어서 B-트리가 있는 문제를 해결하는 방법입니다. , 가지 추가

5. B-Tree

먼저 B 마이너스 트리를 읽지 말고 B 트리를 읽어보세요

모든 키 값은 트리 전체에 분산되어 있습니다.

리프가 아닌 노드에서 검색이 끝날 수 있으며, 전체 키워드 집합 내에서 검색이 수행되며 성능은 이진 검색에 가깝습니다.

각 노드에는 최대 m개의 하위 트리가 있습니다.

루트 노드에는 최소 2개의 하위 트리가 있습니다.

분기 노드에는 최소 m/2개의 하위 트리(루트 노드와 리프 노드를 제외한 모든 분기 노드)가 있습니다.
1. 모든 리프 노드는 동일한 레이어에 있으며, 각 노드는 최대 m-1개의 키를 가질 수 있으며 오름차순으로 배열됩니다.
5. 위 그림과 같이: (그림의 일부만 그려지는데 사실 제한은 없습니다. p1, p2, p3 뿐만 아니라)

각 노드는 하나의 디스크 블록을 차지합니다. 노드에는 오름차순으로 배열된 2개의 키워드와 하위 트리의 루트 노드에 대한 3개의 포인터가 자식 노드가 위치한 디스크 블록 주소를 저장합니다. 두 개의 키워드로 나누어진 세 개의 범위 필드는 세 개의 포인터가 가리키는 하위 트리의 데이터의 범위 필드에 해당합니다. 루트 노드를 예로 들면 키워드는 16과 34이다. p1 포인터가 가리키는 하위 트리의 데이터 범위는 16보다 작고, p2 포인터가 가리키는 하위 트리의 데이터 범위는 16~34이며, 데이터는 16이다. p3 포인터가 가리키는 하위 트리의 범위가 34보다 큽니다. .

키워드 28을 찾는 과정:

1. 루트 노드를 기준으로 디스크 블록 1을 찾아 메모리에 읽어 들입니다. [첫 번째 디스크 I/O 작업]
2. 구간(16, 34)에서 키워드 28을 비교하여 디스크 블록 1의 포인터 p2를 찾습니다.
3. p2 포인터에 따라 디스크 블록 3을 찾아 메모리에 읽어 들입니다. [두 번째 디스크 I/O 작업]
4. 구간(25, 31)에서 키워드 28을 비교하여 디스크 블록 3의 포인터 p2를 찾습니다.
5. 포인터 p2를 기준으로 디스크 블록 8을 찾아 메모리로 읽어옵니다. [세 번째 디스크 I/O 작업]
6. 디스크 블록 8의 키워드 목록에서 키워드 28을 찾으세요.

단점:

1. 각 노드에는 키가 있고 데이터도 포함되어 있으며, 각 페이지의 저장 공간이 제한되어 있습니다. 데이터가 많으면 각 노드가 저장할 수 있는 키 수가 작아집니다.
2. 저장된 데이터의 양이 많으면 깊이가 증가하여 디스크에 대한 IO 쿼리 수가 증가하여 쿼리 성능에 영향을 미칩니다.

6.B+ 트리

B+ 트리는 B-트리를 기반으로 한 최적화입니다. 변경 사항은 다음과 같습니다.

1. B+ 트리의 각 노드에는 더 많은 노드가 포함될 수 있습니다. 첫 번째 이유는 다음과 같습니다. 트리의 높이를 줄이기 위한 것이고, 두 번째 이유는 데이터 범위를 여러 간격으로 변경하기 위한 것입니다. 간격이 많을수록 데이터 검색 속도가 빨라집니다.
2. 비리프 노드는 키만 저장하고, 리프 노드는 키와 데이터를 저장합니다.
3. 리프 노드의 포인터가 서로 연결되어 있어(디스크 미리 읽기의 특성에 맞춰) 순차 쿼리 성능이 더 높습니다.



위 그림과 같이: B+ 트리에는 두 개의 헤드 포인터가 있는데, 하나는 루트 노드를 가리키고 다른 하나는 키워드의 가장 작은 리프 노드를 가리키며 모든 리프 노드(및 데이터 노드) 사이에 체인 링 구조가 있으므로 B+ 세 가지 검색 작업이 있습니다. 하나는 기본 키에 대한 범위 검색 및 페이징 검색이고, 다른 하나는 루트 노드에서 시작하는 무작위 검색입니다.

InnoDB와 MyISAM의 인덱스 차이점

1. InnoDB-기본 키 인덱스

리프 노드는 특정 행 데이터를 저장합니다.



2.InnoDB-비기본 키 인덱스

리프 노드는 기본 키가 아닌 키를 저장합니다. indexes는 기본 키 값입니다(따라서 쿼리 데이터는 기본적으로 테이블에 반환되어야 합니다)



3.MyISAM

리프 노드는 행 데이터의 주소를 저장하므로 추가 주소 지정과 하나의 추가 IO가 필요합니다.



요약: mysql이 B+ 트리를 사용하는 이유

정확한 설명: mysql의 InnoDB 및 MyISAM 스토리지 엔진의 인덱스가 B+ 트리

• 해시 테이블을 사용하는 이유, 동등한 쿼리는 빠르지만 그렇지 않습니다. 공통 범위 검색을 충족하고 인접한 두 값 사이에 관계가 없으며 해싱은 더 많은 메모리를 소비합니다.

• 이진 트리/균형 이진 트리/레드-블랙 트리 등은 모두 가지가 2개밖에 없습니다. 공통점은 데이터의 양이 많을수록 트리의 깊이가 깊어지고 개수가 많아진다는 것입니다. IO가 증가합니다.

• B-트리는 노드에 데이터를 저장하므로 한 페이지에 저장되는 키 수가 줄어들고 트리의 깊이가 늘어납니다.

• B+ 트리의 리프가 아닌 노드에서 데이터가 제거되어 페이지의 키 수가 늘어나고 리프 노드는 연결 목록을 통해 연결되므로 범위 검색 및 페이징에 도움이 됩니다.

원본 주소: https://juejin.cn/post/6994810803643744269

저자: Mr. Ji

더 많은 프로그래밍 관련 지식을 보시려면 프로그래밍 영상을 방문해 주세요! !

위 내용은 mysql 인덱스가 B+ 트리 구조를 사용하는 이유에 대해 심도 있게 이야기해보자.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!