\chapter{Indexの差分Update}
Jungleの木はIndexを持っており、木のCommit時にFull Updateを行っている。
そのため、Commitを行うたびO(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。
なので、高速にIndexの更新を行うため、Index の差分アップデートを実装した。

\section{差分 Updateの実装}
Jungle は木の編集を行う際に、編集を行うノードと、経路にあるノードの複製を行い新しい木構造を構築するため、
Index の中には、編集後の木には存在しない複製前のノードが残ってしまう。
なので、Index の差分 Update を行う際には、それらのノードを Index から削除して、新しく複製されたノードを Index に登録する必要がある。

そのためには、編集を行ったノードを覚えておく必要がある。
そこで、Jungle Tree Editor 内に、編集を加えたノードを覚えておくためのリストを定義した。
Editor は、木に編集を加えたら、リストに編集前のノードを保存する。
そして、Commit 時にリストにあるノードを使って Index の中に残っている、編集後の木に存在しないノードを削除する。
その後、新しく作られたノードを Index に登録して Update は終了する。


\section{編集前のノードの削除}
IndexのUpdateを行う際、初めに、編集後の木に存在しないノードをIndexから削除する。
削除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノードである。
ノードの削除は、以下の手順で行われる。

\begin{enumerate}
\item 編集を行ったノードのリストからノードを取得する。
\item 取得したノードが、保持している値をIndexから削除する。
\item 自身と子供のペアを ParentIndex から削除する。
\item ParentIndex から親を取得する。
\item 2 - 4をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。
\item 1 - 5をリストからノードが無くなるまで続ける。
\end{enumerate}

Parent Index から値が取得できない場合は、自身からルートまでの経路にあるノードは Index から削除されていることが保証されているため、削除を終えて、リストに入っている次のノードの削除処理を行っても構わない。



\section{Indexへのノードの挿入}
Indexから不要なノードを削除した後は、新しく作られたノードをIndexに挿入する。
ノードの挿入は、以下の手順で行われる。

\begin{enumerate}
\item 木からルートノードを取得する。 
\item 取得したノードがIndexに登録されているかを調べる。
\item 登録されている場合、そのノード以下のSub Treeは、全てIndexに登録されているので、次のノードに移動する。
\item 登録されていなかった場合、自身が保持している値をIndexに登録する
\item 自身と子ノードをParent Index に登録する。
\item 自身の子ノードを取得したノードとして2に戻る。
\item 全てのノードを登録したら終了する。
\end{enumerate}


\section{Full Update との使い分け}
Indexの差分Updateは、不要なノードの削除と新しく木に追加されたノードの挿入を行っているため、1ノードに対する処理は Full Updateより大きい。
少ない回数編集を行った後の Commit は、差分Updateの方が高速に行えるが、多くの編集を行った後の Commitだと、Full Updateの方が高速に動作する可能性がある。
これに関しての検証は、性能測定の章に記述する。

\newpage