Mysql-index-BTree 유형 [단순화]

인터넷에서 B-TREE에 대한 요약, b-tree, B-tree, B+ tree, B* tree에 대한 요약을 많이 읽었습니다(Emma는 왜 아직도 4개를 가지고 있나요? 거의 혼란스러울 정도입니다).

그 중 일부는 정말 흥미롭고 감탄스럽기도 하지만, 모두 너무 길어서 부담스럽습니다. 간단하게 요약본을 만들어 간단하고 모바일 방식으로 소개하고 차이점에 대해 이야기해 보겠습니다.
1. B-트리

이진 트리는 이진 트리입니다. (K, h, n의 공식은 여기서 다루지 않습니다. 관심있는 분은 직접 검색해보시면 됩니다..)

(1) 모두 비- 리프 노드 최대 2명의 아들이 있음(왼쪽 및 오른쪽)

(2) 모두 노드 저장키워드;

(3) 리프가 아닌 노드의 왼쪽 포인터 해당 키보다 작은 하위 트리를 가리킵니다. 오른쪽 포인터는 해당 키워드보다 큰 하위 트리를 가리킵니다. (간단히 말하면 왼쪽은 자체보다 작고 오른쪽은 자기 자신보다 크다)

피규어B트리

Two.B-Tree

균형 이진 트리 --AVL 트리 [여기서 B는 실제로 균형을 의미합니다~]

( 1) 루트 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 깊이는 최대 1만큼 다릅니다. (이렇게 하면 루트 노드에서 극단적인 현상이 발생하지 않습니다. 위 그림의 오른쪽)

(2) 루트 노드의 왼쪽 하위 트리와 오른쪽 하위 트리는 모두 균형 이진 트리입니다. .

(3) 모든 노드 스토어 키워드;

삽입된 시퀀스가 ​​무엇이든 이진 트리의 각 노드의 균형 인자가 1보다 크지 않도록 조정을 통해 균형 잡힌 이진 트리를 구축할 수 있습니다.

트리의 깊이가 가장 얕은 에 도달하도록 보장하므로 비교 횟수가 줄어들고 시간 복잡도가 줄어듭니다

Figure B-Tree

쓰리.비+트리

B+의 검색은 B-tree의 검색과 기본적으로 동일합니다. 차이점은 B+ 트리는 리프 노드만 적중합니다(B-트리는 리프가 아닌 노드에도 적중할 수 있음)

(1) 모든 키워드는 리프 노드의 연결 리스트(dense index)에 나타나며, 연결 리스트의 키워드는 순서대로 나타납니다( 루트 노드만 키워드를 저장하고 마지막 트리의 끝에 값이 있습니다 )

(2) Non- 리프 노드는 리프 노드 인덱스(희소 인덱스)에 해당하고, 리프 노드는 (키워드) 데이터를 저장하는 데이터 계층에 해당합니다. ( 루트가 아닌 노드는 실제로 루트 노드를 가리키는 인덱스를 저장합니다 )

(3 ) 처음 두 점으로 인해 이 리프가 아닌 노드에 데이터를 저장하는 것은 불가능합니다. (B-의 세 번째 차이점)

(4) 루트 노드에도 가로로 체인 포인터가 있습니다(따라가기 편리합니다) 단서는 빨리 찾을 수 있지만 그런 포인터가 없고, 다음 값이 인접한 이웃이더라도 원을 그리며 달려야 얻을 수 있습니다)

참고로 우리가 흔히 사용하는 대부분의 인덱스 결과, 혹은 우리가 흔히 말하는 B-TREE 구조는 B+ 구조를 참고하세요~~

그림B+나무

4. B* 트리
는 B+트리 변주곡,

(1)B+트리의 루트 및 리프가 아닌 노드는 형제에 포인터를 추가합니다. non-root 노드는 수평 연결 리스트도 추가합니다.]

그림B*나무

5. 요약:

B 트리: 이진 트리,

각 노드에는 하나의 키워드만 저장됩니다. 작으면 왼쪽 노드로 이동하고, 크면 오른쪽 노드로 이동합니다. ( 그러나 여러 번의 삽입과 삭제 후에 B-트리는 다른 구조로 이어질 수 있습니다 ) 이러한 이유로 B-트리라고도 알려진 균형 알고리즘을 추가한 후 균형 이진 트리가 생성됩니다. 🎜>

B-트리: B-트리 기반, 밸런싱 알고리즘 및 다중 경로 검색 트리 추가 ,

1. 각 노드에는 M/2~M개의 키워드가 저장됩니다.

2. 키워드 범위를 가리키는 하위 노드;

3. 모두 키워드는 전체 트리에 한 번만 나타납니다.

4. 리프 노드와 리프가 아닌 노드가 적중될 수 있습니다(데이터 저장 여부).

B+ 트리: B-트리 기반,

1. 리프 노드에 연결리스트 포인터 추가 2. 키워드는 리프 노드에 나타납니다.

3. 리프가 아닌 노드는 리프 노드의 인덱스 역할을 합니다.

4. 리프 노드:

B+ 트리를 기반으로 연결 리스트 포인터

도 리프가 아닌 노드에 추가되어 노드의 최소 활용도가

질문: B*가 더 효율적인데 왜 b* 트리가 덜 사용된다고 생각하시나요? ????아니면 어디에 유용한가요? ? 아마도 아직은 너무 부족한 것 같아요. . 서로에 대해 더 잘 아는 아동화는 서로 배울 수 있으니 조언 부탁드립니다. 미리 감사드립니다~답변:
최근에 사람이 있다는 걸 알았습니다.

Reiser4의 파일 시스템

이 이 구조를 사용하는 것 같습니다. 저자

한스 라이저,

아내가 자신을 불륜으로 만들었다는 이유로 아내를 죽이고 감옥에 갔는데, 이는 프로젝트 진행에 직접적인 영향을 미쳤다. . .

소개:

Linux 파일 시스템 ReiserFS 저자 Hans Reiser가 아내 살해 혐의로 15년 징역형을 선고받은 후에도 ReiserFS의 개발은 멈추지 않았습니다. 아직 병합되지 않았습니다. Linux 메인 브랜치로 이동하세요. 소규모 개발자 그룹은 여전히 ​​ReiserFS의 네 번째 버전(줄여서 Reiser4)을 계속 개발하고 있습니다. 지난 달에 새 버전을 출시했습니다, Linux3.5.4 커널을 지원합니다.

위 내용은 Mysql-index-BTree 형태의 [단순화] 내용이며, 더 많은 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고하시기 바랍니다. )!