Btree 인덱스의 원리는 무엇입니까

Btree 인덱스의 원리는 이진 트리가 논리적으로 매우 가까운 노드가 물리적으로 매우 멀리 떨어져 있어 IO 수가 높고 검색 효율성이 높다는 것입니다. low; Btree는 데이터를 쿼리할 때 발생하는 노드 수를 줄이기 위해 여러 분기 노드를 활용할 수 있는 균형 잡힌 "m-way" 검색입니다.

BTree 인덱스 원리

이진 트리는 매우 높은 트리 높이, 논리적으로 가까운 노드, 물리적으로 매우 멀리 떨어져 있으며 지역성을 활용할 수 없음, 높은 IO 시간, 낮은 검색 효율성을 초래합니다.

Btree는 a 다중 분기 노드(하위 트리 노드)를 사용하여 데이터를 쿼리할 때 경험하는 노드 수를 줄여 액세스 시간을 절약할 수 있는 균형 잡힌 m-way 검색 트리입니다. m을 B-Tree의 차수라고 합니다.

B 트리는 2-3 검색 트리의 확장으로 볼 수 있습니다. 즉, 각 노드가 M-1 하위 노드를 가질 수 있습니다.

Features

• 루트 노드가 하나 있고 루트 노드에 레코드가 하나만 있고 하위 노드가 두 개 있거나 루트 노드가 비어 있습니다.

• 각 노드 레코드의 키와 포인터가 서로 떨어져 있습니다. , 포인터는 하위 노드를 가리킵니다.

• d는 트리의 너비를 나타냅니다. 리프 노드를 제외하고 각 노드에는 [d/2, d-1]개의 레코드가 있으며 이 레코드의 키는 배열됩니다. 크기에 따라 왼쪽에서 오른쪽으로 [d/2+1,d]개의 하위 항목이 있습니다.

• 한 노드에서 n번째 하위 트리의 모든 키는 이 노드의 n번째 키보다 작습니다. n-1번째 키보다

• 모든 리프 노드는 동일한 수준에 있어야 합니다. 즉, 동일한 깊이를 가져야 합니다.

• B-Tree의 특성상 키별로 데이터를 검색하는 알고리즘이 있습니다. B-Tree의 경우 매우 직관적입니다. 먼저 루트 노드부터 진행합니다. 이진 검색을 하면 해당 노드의 데이터를 반환하고, 그렇지 않으면 해당 간격에서 포인터가 가리키는 노드를 해당 노드를 찾을 때까지 재귀적으로 검색합니다. 널 포인터가 발견되었습니다. 전자는 성공하고 후자는 실패합니다.

추천: "mysql 튜토리얼"

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