Blink ツリーに挿入を行うと、ルート ノードからリーフ ノードへのパスが格納されます。子ノードが分割されると、そのような変更が親ノードに伝播されます。伝播がスレッド A のルート ノードを調査し、現在の挿入がスタック (パスを格納するために使用される) をチェックし、スタックの一番下のノードが「ルート」であることを検出するとします。また、「ルート」も分割する必要があります。新しいルートを作成します。
では、「ルート」がすでに別のスレッドによって分割されていて、「ルート」が現在の本当のルートではない場合はどうなるでしょうか。したがって、スレッド A によって行われる新しいルートの作成は正しくありません。
ブリンクツリーはこのような状況にどのように対処しますか?
著者がその問題をどのように処理するつもりだったのかはわかりません (そして、それは本当だと思います)。1 つの可能性は、ツリーの高さ (深さ) と葉の上の各高さの最初のブロックのアドレスを含むヘッダー ブロックを追加することです。スタックの最後を使い果たした場合は、このブロックをロックして読み取り、新しいルート (より正確には、スタック内のツリーの高さより上の高さにある最初のブロック) を特定する必要があります。そこにある場合は、ヘッダー ブロックのロックを解除し、続行する前にブロックをスタックに追加します。新しいルートが存在しない場合は、(新しいルートを書き込んだ後) インデックス ブロックを書き戻す前に、それを作成してヘッダー ブロックに追加できます。理論的には、ルートがアップ フェーズとダウン フェーズの間で複数回分割された場合、これは複数回発生する可能性があります。