배열은 이미 균형 잡힌 B- 트리입니다. 사실입니까?

Question

한 포럼에서 배열은 이미 균형 잡힌 B- 트리라고 들었습니다. 어떻게 얻습니까? B 트리의 요소 추가에 고정 된 복잡성이 있기 때문일 수 있습니다.

Answer 1

순전히 데이터 구조의 관점에서 정렬 된 배열 a은 하나의 노드 만있는 B- 트리로 간주 될 수 있습니다. 즉, length보다 큰 B 트리가 a입니다. 이 경우 루트 노드는 배열 a이 될 것이고 트리에 노드가 하나만 있기 때문에이 루트 노드는 리프 노드가됩니다. 이는 키뿐만 아니라 데이터도 보유한다는 것을 의미합니다.

균형 B 트리에서 모든 리프 노드가 동일한 깊이에 있어야한다는 요구 사항을 만족하는 깊이 0에 노드가 하나만 있기 때문에 그러한 B 트리가 균형을 유지합니다.

위해 m의 B-트리 모든 노드가 최대 미터에게 아이가있는 B-나무가있는 곳은 질서의 정의를 개최한다. 즉, 노드는 최대 m -1 키 (또는 리프 노드의 경우 요소)를 포함 할 수 있습니다.

Answer 2

B- 트리에 대해서는 잘 모르지만, 정렬 된 배열은 이진 탐색 트리의 균형이 잡힌 구조를 가지고 있다는 것이 잘 알려져 있습니다. 크 누스 등에 있습니다.

확장자가 low에서 high까지 인 부분 (보통 때와 같이 한 끝을 가리키며)을 생각해보십시오. 나무의 뿌리는 (low + high)/2에 있습니다 (그 색인은 mid이라고 부릅시다). 왼쪽 하위 트리는 low에서 mid까지 확장됩니다. 오른쪽 하위 트리는 mid + 1에서 high까지 확장됩니다. 길이가 0 인 범위는 잎과 일치합니다.

중간에 왼쪽의 요소는 <=이며, 배열은 정렬되어 있으므로 루트 요소이므로 왼쪽 트리의 요소와 정확히 일치합니다. 오른쪽에서도 똑같이 작동합니다.

또한 왼쪽과 오른쪽 하위 트리의 평균 길이가 같기 때문에 암시 적 트리가 균형을 유지해야한다는 것을 알 수 있습니다.

Answer 3

PHP로 테스트하기 전에이 문제를 테스트했습니다. 나는 18000 로그 레코드를 임시 테이블에 삽입하고 쿼리를 수행 한 다음 이러한 로그 레코드를 배열에 추가합니다 (연관이 있음). 그리고 다시 같은 쿼리를 수행합니다. 전자는 0.006 초, 평균은 0.51 초 걸렸다. 그래서 연관 배열은 적어도 PHP에서는 b-treed가 아니라고 생각합니다.