B-Tree의 노드는 어떤 데이터 구조를 사용합니까?</p>가 <p>(1) 모든 노드에 가지고 누스의 정의에 따라

Question

, 차수 m의 B 트리 (각 노드의 자식의 최대 번호)를 다음 특성을 만족 나무라 대부분의 아이들.

(2) 모든 노드 (루트를 제외하고)는 적어도 ⌈m/2 *의 하위 노드를가집니다.

(3) 리프 노드가 아닌 루트는 적어도 두 개의 자식을가집니다.

(4) k 개의 자식이있는 리프가 아닌 노드는 k-1 개의 키를 포함합니다.

(5) 모든 잎은 같은 레벨에 나타나고 정보를 전달합니다.

출처 : B-나무의 Wikipedia

일부 시각화 같이이 시각화에서

, 나는 적어도 각 노드가 배열 자료 구조를 가지고 있다고 생각 (또는 것 비슷한 것).

기타는 다음과 같다 : 는

이리스트 같은 자료 구조로 오히려 보인다.

그래서 제 질문은 :

B-나무는 어떤 자료 구조를 사용합니까?

내 알고리즘 클래스의 사용 예는 데이터베이스와 파일 시스템입니다. 누구든지 SQLite이 B-tree 노드를 구현하는 방법을 알고 있습니까? 또는 ext3? 또는 다른 (잘 알려진) 실제 예입니다.

Answer 1

B- 트리 자체는 데이터 구조 (indexstructure)입니다. 여기 (이것이 좋은 excersize이며, 필요한 방법과 몇 가지 필요한 정의없이!)는 의사 코드 예제입니다

노드의 바디 :

class BNode 
{ 
    int keys[]; 
    BNode children[]; 

    public BNode() {} 

    public BNode() {} 

    public int getValue(int key) {} 

    public BNode getChildren(int key) {} 
} 

그리고 B-트리의 몸 :

현실 세계에서

class BTree 
{ 
    BNode root; 

    BTree() 
    { 
     root = new BNode(null); 
    } 

    BNode search(int key) {} 

    void insert(int key) {} 

    void delete(int key) {} 
} 

---

:의

Here is the B-Tree implementation PostgreSQL (데이터베이스 색인화에 사용됨).