天天看點

B樹 B-Tree | Set 1 (Introduction)What is the difference btw “Order” and “Degree” in terms of Tree data structureB+ tree

介紹B樹之前,先介紹樹的幾個概念。

Degree

  The number of subtrees of a node.

Height of node

  The height of a node is the number of edges on the longest path between that node and a leaf.

Height of tree

  The height of a tree is the height of its root node.

Depth

  The depth of a node is the number of edges from the tree's root node to the node.

B樹 B-Tree | Set 1 (Introduction)What is the difference btw “Order” and “Degree” in terms of Tree data structureB+ tree

定義

A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon disk block size.

  1. Every node except root must contain at least t-1 keys. Root may contain minimum 1 key.
  2. All nodes (including root) may contain at most 2t – 1 keys.
  3. Number of children of a node is equal to the number of keys in it plus 1.
  4. All keys of a node are sorted in increasing order.
  5. All leaves are at same level.

另一種定義方式

B樹 B-Tree | Set 1 (Introduction)What is the difference btw “Order” and “Degree” in terms of Tree data structureB+ tree

 4階B樹又叫2-3-4樹,3階B樹又叫2-3樹。

B樹 B-Tree | Set 1 (Introduction)What is the difference btw “Order” and “Degree” in terms of Tree data structureB+ tree
B樹 B-Tree | Set 1 (Introduction)What is the difference btw “Order” and “Degree” in terms of Tree data structureB+ tree

參考資料:

https://en.wikipedia.org/wiki/Tree_(data_structure)

https://en.wikipedia.org/wiki/B-tree#Definition

B-Tree | Set 1 (Introduction)

What is the difference btw “Order” and “Degree” in terms of Tree data structure 

B+ tree

繼續閱讀