Mercurial > hg > Papers > 2017 > tatsuki-master
view introduciton.tex @ 3:6f9f9669b264
commit
author | tatsuki |
---|---|
date | Sun, 29 Jan 2017 11:57:18 +0900 |
parents | da6a6eba893d |
children | 2d92c3e9fd31 |
line wrap: on
line source
\chapter{研究目的} \pagenumbering{arabic} プログラムからデータを分離して扱うデータベースには、 プログラム中のデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。 データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 データベース自体も、表に特化したKey Value Store、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 そこで当研究室では、煩雑な設計を行わずプログラム内部に木構造を格納できるデータベースJungleを提案している。 また、Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、 木のルートをアトミックに入れ替えることでトランザクションを実現する。 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 Jungleは分散構成も可能である。 Jungleは、様々の形の木構造を格納できるが、形によっては木の変更の手間が大きくなるなどの問題がある。 そこで、本研究では、今までの汎用的な木ではなく、特定の形の木を格納することに特化した機能を実装した。 また、Index等の木の編集時にネックとなっていた箇所にも改善を行った。 その結果、木の更新速度を大幅に向上させることに成功した。 \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 章では、今回実装した機能の測定について記述する。