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

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

Jungleは、読み込みは高速に行える反面、書き込みは木の形に依存しており、最悪の場合O(n)となってしまう。
また、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 章では、今回実装した機能の測定について記述する。