四十三庵

蔀の雑記帳

B Tree(B木)

データ構造とアルゴリズム (新・情報 通信システム工学)

ノート

  • balanced treeの例
  • A B-Tree of order n satisfies the following properties:
    • Every node has at most 2n keys.
    • Every node (except root) has at least n keys.
    • Every non-leaf node with k keys has k+1 children.
    • The keys in all nodes are sorted in increasing order.
    • The subtree between two keys k and l of a non-leaf node contains all the keys between k and l.
    • All leaves appear at the same level.
  • A second order B-Tree with keys from 1 to 20 looks like this:

f:id:st43:20200411112752p:plain

  • 日本語版Wikiと英語の解説が何か合わない気がする
  • 合ってるのかこれ?
  • 2-3木はオーダー3のB木
  • 実装例までは追えず