mysql 인덱스의 데이터 구조는 무엇입니까

1. 소개

mysql 인덱스의 데이터 구조는 트리이며, 일반적으로 사용되는 스토리지 엔진 innodb는 B+Tree를 사용합니다. 다음은 B+Tree 및 관련

검색 트리에 대한 간략한 소개입니다.

2. 다양한 검색 트리

1. 이진 정렬 트리(이진 검색 트리라고도 함)

이진 정렬 트리는 가장 간단한 검색 트리입니다. b) 왼쪽 하위 트리에 있는 모든 노드의 값은 상위 노드의 값보다 작고, 오른쪽 하위 트리에 있는 모든 노드의 값은 상위 노드의 값보다 큽니다.

2. 균형 이진 트리(AVL 트리라고도 함)

균형 이진 트리는 트리 깊이를 제한하여 검색 비교 횟수를 줄이는 이진 정렬 트리를 기반으로 합니다. a)는 이진 트리입니다.

b) 왼쪽 하위 트리에 있는 모든 노드의 값은 상위 노드의 값보다 작고, 오른쪽 하위 트리에 있는 모든 노드의 값은 상위 노드의 값보다 큽니다. ;

c) 왼쪽 자식의 값 트리와 오른쪽 하위 트리의 깊이 차이는 -1, 0, 1 이내이고, 그렇지 않으면 하위 트리가 회전됩니다.

3. B-트리(B-Tree)

B-트리는 균형 이진 트리와 비교할 때 부모 노드의 직접 자식 노드 수가 더 이상 제한되지 않습니다. 2,

m(custom)을 지정하면 트리 깊이를 크게 늘리지 않고도 더 많은 노드를 저장할 수 있습니다.

B-트리는 일반적으로 파일 시스템에서 사용됩니다.

기능:

a) 트리의 각 노드에는 최대 m(사용자 정의) 하위 노드가 있습니다.

b) 루트 노드가 리프 노드가 아닌 경우 최소 2개의 하위 노드가 있습니다.

c) 모두 루트 노드를 제외한 리프가 아닌 노드는 전체 하위 노드의 최소 m/2를 갖습니다.

d) 상위 노드 아래 가장 왼쪽 하위 트리에 있는 모든 노드의 값은 상위 노드의 최소값보다 작습니다.

가장 오른쪽 하위 트리에 있는 모든 노드의 값은 상위 노드의 최대값보다 크고,

나머지 중간 하위 트리에 있는 모든 노드의 값은 상위 노드의 양쪽 값 사이에 있습니다. 포인터의 노드;

e) 모든 리프 노드는 동일한 레이어에 있습니다.

참고: 모든 노드는 ​​

4, B+ 트리(B+Tree)

B+ 트리는 B-트리입니다. B-트리를 기준으로 리프 노드의 값은 모든 상위 노드의 값이 리프 노드의 반복 값을 포함하며, 상위 노드는 인덱스 검색 역할만 합니다. 노드는 또한 순서가 지정된 연결 목록을 형성합니다.

mysql의 스토리지 엔진은 innodb의 인덱스이고, 사용되는 데이터 구조는 B+ 트리입니다.

특징:

a) m개의 하위 노드가 있는 상위 노드에는 m개의 키워드가 있습니다.

b) 모든 리프 노드에는 모든 키워드(값)가 포함되어 있으며 작은 것부터 큰 것까지 순서가 지정된 연결 목록을 형성합니다.

c) 모두 비 -리프 노드는 인덱스 역할을 하며 노드에는 하위 트리에 있는 모든 노드의 최대값만 포함됩니다.

d) 모든 리프 노드는 동일한 레벨에 있습니다.

참고: 리프 노드에는 모든 키워드(값)가 포함됩니다.

5. B*트리(B*Tree)

B* 트리는 B+ 트리의 변형으로, 동일한 레이어의 리프가 아닌 노드에 대한 포인터가 추가됩니다. 같은 레이어의 노드들도 연결리스트를 구성합니다.

3. 요약

정리하자면, 위의 검색 트리는 서로 연관되어 있습니다.

mysql의 innodb 인덱스로 귀결되는데, 이는 기본 키를 통해 데이터를 집계하고 B+ 트리를 사용하여 구현하는 클러스터형 인덱스와 같은 B+ 트리입니다.

mysql의 인덱스이자 데이터 저장 구조입니다. 노드에는 모든 데이터가 포함되며 리프가 아닌 노드는 인덱스 역할만 합니다(기본 키가 정의되지 않은 경우 innodb는 기본 키를 클러스터형 인덱스로 암시적으로 정의합니다).

더 많은 MySQL 관련 기술 기사를 보려면

MySQL Tutorial

칼럼을 방문하여 알아보세요!

위 내용은 mysql 인덱스의 데이터 구조는 무엇입니까의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!