\chapter{データベースJungleに\\新たに追加した構成要素}
本章では、今回効率的な木の非破壊アップデートを可能にするために追加した機能である、
Jungleの中で使用する非破壊赤黒木、Indexの差分アップデート、Differential Jungle Tree、Red Black Jungle Treeについて大まかな説明する。


\section{非破壊 Red Black Treeの実装}
JungleのIndexは、Java上で関数型プログラミングが行えるFunctional Java の非破壊 TreeMapを使って実装されていた。
しかし、Functional Javaは、処理が重く、実用的な性能ではなかったため、非破壊の TreeMap の実装を新しく行った。

\section{Indexの差分 Update}
Jungleは、Indexの更新をCommit時に Full Updateで行っている。
そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっている。

Index の更新処理を高速に行えるようにするため、
前の木との差分だけIndexを更新する機能を Jungle に追加した。


\section{Differential Jungle Treeの実装}
Jungleの木の変更の手間は木の形によって異なる。
特に線形の木は、変更の手間がO(n)となってしまう。
線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。
しかし、PushPopは木の並びが逆順になってしまうため、正順の木を構築する際には使用できない。
その問題を解決するために、Differential Jungle Treeの実装を行った。
Differential Jungle Treeは、木のバージョンごとに、自身の末尾のノードを保持する。

Differential Jungle Tree は、木を破壊的に更新するが、編集・検索時に、末尾ノードを使用することで、過去の木の形を残すことが可能となっている。


\section{Red Black Jungle Tree}
Jungle は、木に編集を加えた際、編集を加えたノードと、経路にあるノードの複製を取る。
その為、木の編集の手間は、木の大きさにも依存している。
最適なバランスの取れた木構造を構築することで、編集の手間をn(logN)にすることは可能だが、
Default Jungle Tree だと、木の形をユーザーが Path を用いて、バランスを取る必要ある。
しかし、ユーザーが全ての木構造の形を把握し、バランスの取れた木を構築するのは難しい。
そこで、自動で木のバランスを取り、最適な木構造を構築する機能を Jungle Tree に実装した。
バランスは、木の生成時に特定の {\tt Balance Key} 決定し、それを使って行う。

木の探索に関してはBalanceKeyを用いた場合N(Logn)、そうでない場合はO(n)で行える。