\chapter{ソフトウェア内部で使用するのに適した 木構造データベース Jungle}
\pagenumbering{arabic}
プログラムからデータを分離して扱うデータベースには、
プログラム中のデータ構造と表構造のミスマッチという問題がある。
例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。
プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。
レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術、
データベース自体を表に特化したKey Value Store技術、PostgreSQLやMySQLにJsonなどの不定形のデータ構造を格納技術
が開発されてきたが、これを本質的には解決することはできていない。
この問題はデータベースのインピーダンスミスマッチと呼ばれている。
不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理するのは
並列処理が中心となってきている今のアプリケーションには向いているとは言えない。
そこで当研究室では、これらの問題を解決するためにプログラム内部に木構造を格納できるデータベース Jungle を提案している。
Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、
木のルートをアトミックに入れ替えることでトランザクションを実現する。
プログラムは、この木を内部のデータ構造として直接取り扱うことができる。
Jungleは、全体の整合性ではなく、木ごとに閉じた局所的な整合性を保証している。
また、整合性のある木同士をマージすることで新しい整合性のある木を作り出すことも可能であるため、データの伝搬も容易である。


\section{本論文の構成}

Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。
また、Indexの構築も大幅なネックとなっていた。
そこで、本研究では、Jungleの木とIndexの編集機能の改善を行う。
また、実際にJungleを使用した複数のアプリケーション作成し評価を行う。

本論文の構成は以下のようになっている。
\begin{itemize}
\item 第2章で既存のデータベース
\item 第3章ではJungleの基本的な機能・API
\item 第4章ではJungleに新しく加えた構成要素
\item 第5章では改良後のIndexの実装に使用する非破壊 TreeMap の実装
\item 第6章ではIndexの差分 Update の実装
\item 第7章では線形の木を、正順でO(1)で構築することが可能な、Differential Jungle Tree の実装
\item 第8章では自身が Index としての機能を持つ、 Red Black Jungle Treeの実装
\item 第9章では実際に Jungle を使用した、例題アプリケーションの実装
\item 第10章では今回実装した機能の測定
\end{itemize}