PostgreSQLのfsm_search_avail()がFSMのバイナリツリーを探索している例をMermaidで図示してみる

# 前提
以下の Free Space Map (FSM) のバイナリツリーにおいて、minvalue = 7 の空き容量のページを探索する。
```mermaid
graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
```

# 探索
1. ルートの N0(=7) が minvalue(=7) 以上のため探索を継続する
    * もし N0 が minvalue より小さければ、このツリーからは minvalue の空き容量のページを探せないため、探索を打ち切る
   ```mermaid
   graph TB;
    N0(("`**N0:7**`"))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    style N0 fill:pink
   ```
1. N0 から N12 に fp_next_slot で移動する
    * 今回は fp_next_slot が N12 を指していたとする
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12(("`**N12:6**`"))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    N0==>|fp_next_slot|N12
    style N12 fill:pink
   ```
1. N12(=6) が minvalue(=7) より小さいため、N12 から右の N13 に rightneighbor() で移動する
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13(("`**N13:5**`"))
    N6-.->N14((N14:2))
    N12==>|"rightneighbor()"|N13
    style N13 fill:pink
   ```
1. さらに N13 の親の N6 に parentof() で移動する
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6(("`**N6:5**`"))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    N13==>|"parentof()"|N6
    style N6 fill:pink
   ```
1. N6(=5) が minvalue(=7) より小さいため、N6 から右の N3 に rightneighbor() で移動する
    * 右端から rightneighbor() すると同じレベルの左端に移動する
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3(("`**N3:5**`"))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    N6==>|"rightneighbor()"|N3
    style N3 fill:pink
   ```
1. さらに N3 の親の N1 に parentof() で移動する
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1(("`**N1:7**`"))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    N3==>|"parentof()"|N1
    style N1 fill:pink
   ```
1. N1(=7) が minvalue(=7) 以上のため、下から上への探索を終了する。次は上から下に探索する
1. N1 から左の子の N3 に leftchild() で移動する
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3(("`**N3:5**`"))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    N1==>|"leftchild()"|N3
    style N3 fill:pink
   ```
1. N3(=5) が minvalue(=7) より小さいため、N3 から右の N4 に ++ で移動する
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4(("`**N4:7**`"))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    N3==>|"++"|N4
    style N4 fill:pink
   ```
1. N4(=7) が minvalue(=7) 以上のため、N4 から左の子の N9 に leftchild() で移動する
    * 親の N1 が minvalue 以上なのに、子の N3 と N4 ともに minvalue より小さい場合は FSM が壊れているので、修復して、探索を最初からやり直す
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9(("`**N9:5**`"))
    N4-.->N10((N10:7))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    N4==>|"leftchild()"|N9
    style N9 fill:pink
   ```
1. N9(=5) が minvalue(=7) より小さいため、N9 から右の N10 に ++ で移動する
   ```mermaid
   graph TB;
    N0((N0:7))-.->N1((N1:7))
    N0-.->N2((N2:6));
    N1-.->N3((N3:5))
    N1-.->N4((N4:7))
    N2-.->N5((N5:6))
    N2-.->N6((N6:5))
    N3-.->N7((N7:4))
    N3-.->N8((N8:5))
    N4-.->N9((N9:5))
    N4-.->N10(("`**N10:7**`"))
    N5-.->N11((N11:2))
    N5-.->N12((N12:6))
    N6-.->N13((N13:5))
    N6-.->N14((N14:2))
    N9==>|"++"|N10
    style N10 fill:pink
   ```
1. N10(=7) が minvalue(=7) 以上かつリーフのため、探索を終える。N10 が探索結果となる