B-Tree

Preface

I feel that YanWeiMin's data structure is about BTree The operation of is too ideal . In particular, the sibling nodes for deleting operations . Then move the maximum and minimum up . I feel very wordy . So I abstracted several meta operations . Both insert and delete can be converted by this . With down In fact, there is no need to find the minimum leaf node to exchange after the operation . You can delete the value all the way down To the bottom .

Meta operation

• split operation

• pull operation

• down operation

• check operation Check for conformity B-Tree The nature of the tree

Delete and insert operations （ recursive ）

• insert

  • Operational elements

    • Current work node n
    • State quantity tag

  • Definition

    • n It's empty ： Create a leaf node ,tag = 2
    • tag = 0 ： return
    • tag =1 ： Update child nodes ,tag=0
    • tag = 2：pull operation
      • check For false ：split operation , tag = 2
      • check It's true ：tag=1

• delete

  • Operational elements

    • Current work node n
    • State quantity tag

  • Definition

    • After deleting check It's true ：tag=0, return
    • After deleting check For false ：tag=1, return
    • tag=0: return
    • tag=1: Update child nodes
      • check It's true tag=0 return
      • Brother node is ⌈m/2⌉： Yes n node split, Again down operation ,tag=1
      • Sibling node subtree >⌈m/2⌉： Yes n node split, Again down operation , Then the sub nodes split, Again pull operation .tag=1