요소의 크기가 다른 경우 B-Tree 불변성을 유지하는 방법은 무엇입니까?

Question

순서 m의 B- 트리의 경우, 루트를 제외한 모든 노드는 m-1 내지 2m-1 요소를 포함해야하며, 여기서 모든 요소는 적어도 하나의 키이고 임의의 추가 데이터 (예를 들어, 값) 일 수도있다. 그러나 기본 블록 장치에서 우수한 성능을 발휘하려면 각 노드가 일정한 전체 크기를 선택해야합니다. 요소가 가변적 인 경우 어떻게됩니까?

SQLite3에는 추가 블록 크기의 조각을 노드에 고정시키는 계획이있는 것 같습니다. MySQL에서는 레코드의 크기를 선언 할 수 있습니다 (예 : 문자열을 입력 할 수도 있고 크기가 작은 문자열을 입력 할 수도 있습니다) . 거기에 다른 해결책이 있습니까? 그리고 사람들이 다른 사람을 뽑을 때 무엇을 생각합니까?

편집 : 그리고 이전 문장에 의해, 내 말은, 데이터베이스 개발자가 가 B-나무 다른 이상 하나의 방법을 구현하기로 결정하는 경우에 대해 어떻게 생각합니까?

(나는 지금 데이터베이스의 과정에서, 그래서 내가 특정 시스템의 세부 사항에 비해 이론 및 설계 각도에 더 관심이 있어요.)

Answer 1

나는 이것이 아주 좋은 질문이라고 생각합니다. RDBMS 벤더는 모두 약간 다른 구현 방식을 가지고 있지만 기본 이론은 동일하며 벤더 선택에 결정적인 요인으로 b 트리 구현을 사용하는 사람은 거의 없을 것입니다.

제가 이해 하듯이, 각 b-tree 페이지의 기본 구조는 키와 포인터를 포함하고 있습니다. 포인터는 계속해서 더 많은 키와 포인터를 포함하는 다른 페이지를 참조하며, 최종 포인터는 연관된 데이터 레코드를 참조합니다.

가변 길이 키를 처리하는 방법은 흥미 롭습니다. 아마도 다른 업체에서는 특정 공급 업체별 솔루션에 대해 설명 할 수 있습니다.

Answer 2

SQL Server는 페이지 크기가 8192 바이트 인 키 길이가 최대 900 바이트입니다. 실제로 900 바이트 키가있는 경우 색인의 중간 수준 페이지에 9 (또는 8) 개의 행만 맞습니다. 이것은 단지 분기 인수가 평소보다 낮다는 것을 의미합니다. 이것은 이론적 인 B-tree invariant에 위배 될 수 있지만 이는 중요한 방식으로 성능을 저해하지 않는 학문적 관심사 일뿐입니다. 그것은 관련된 알고리즘의 점근 적 복잡성을 변화시키지 않습니다.

간단히 말해서 : 이것은 학구적 인 관심사입니다.