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

前提

以下の Free Space Map (FSM) のバイナリツリーにおいて、minvalue = 7 の空き容量のページを探索する。

探索

1. ルートの N0(=7) が minvalue(=7) 以上のため探索を継続する
   • もし N0 が minvalue より小さければ、このツリーからは minvalue の空き容量のページを探せないため、探索を打ち切る
2. N0 から N12 に fp_next_slot で移動する
   • 今回は fp_next_slot が N12 を指していたとする
3. N12(=6) が minvalue(=7) より小さいため、N12 から右の N13 に rightneighbor() で移動する
4. さらに N13 の親の N6 に parentof() で移動する
5. N6(=5) が minvalue(=7) より小さいため、N6 から右の N3 に rightneighbor() で移動する
   • 右端から rightneighbor() すると同じレベルの左端に移動する
6. さらに N3 の親の N1 に parentof() で移動する
7. N1(=7) が minvalue(=7) 以上のため、下から上への探索を終了する。次は上から下に探索する
8. N1 から左の子の N3 に leftchild() で移動する
9. N3(=5) が minvalue(=7) より小さいため、N3 から右の N4 に ++ で移動する
10. N4(=7) が minvalue(=7) 以上のため、N4 から左の子の N9 に leftchild() で移動する
    • 親の N1 が minvalue 以上なのに、子の N3 と N4 ともに minvalue より小さい場合は FSM が壊れているので、修復して、探索を最初からやり直す
11. N9(=5) が minvalue(=7) より小さいため、N9 から右の N10 に ++ で移動する
12. N10(=7) が minvalue(=7) 以上かつリーフのため、探索を終える。N10 が探索結果となる