\chapter{研究目的}
\pagenumbering{arabic}
プログラムからデータを分離して扱うデータベースには、
プログラム中のデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。
データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、
データベース自体も、表に特化したKey Value Store、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。

そこで当研究室では、煩雑な設計を行わずプログラム内部に木構造を格納できるデータベースJungleを提案している。
また、Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、
木のルートをアトミックに入れ替えることでトランザクションを実現する。
プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。
Jungleは分散構成も可能である。

Jungleは、様々の形の木構造を格納できるが、形によっては木の変更の手間が大きくなるなどの問題がある。
そこで、本研究では、今までの汎用的な木ではなく、特定の形の木を格納することに特化させ、
また、Index等の木の編集時にネックとなっていた箇所にも改善を行った。

その後Jungleを使用した例題アプリケーションを作成し、Jungleを実際に運用した際にどのような問題が発生するかの洗い出しを行った。

\section{本論文の構成}
本論文では、初めに既存のデータベースとインピータンスミスマッチについて記述する。
第 3 章では、Jungleの基本的な機能・APIについて記述する。
第 4 章では、Indexの実装に使用する非破壊 TreeMap の実装について記述する。
第 5 章では、Indexの差分 Update の実装について記述する。
第 6 章では、線形の木を、正順でO(1)で構築することが可能な、Differential Jungle Tree の実装について記述する。
第 7 章では、自身が Index としての機能を持つ、 Red Black Jungle Treeの実装について記述する。
第 8 章では、実際に Jungle を使用した、例題アプリケーションの実装について記述する。
第 9 章では、今回実装した機能の測定について記述する。