# HG changeset patch # User tatsuki # Date 1485658638 -32400 # Node ID 6f9f9669b264c71c1c3738cdebbe5f9c2205d064 # Parent 90e06e17ca6bfda9007958a384a6675d7e5aa6ea commit diff -r 90e06e17ca6b -r 6f9f9669b264 abstract.tex --- a/abstract.tex Sat Jan 28 19:28:01 2017 +0900 +++ b/abstract.tex Sun Jan 29 11:57:18 2017 +0900 @@ -1,3 +1,13 @@ \begin{abstract} -アブストラクトを書く +Jungleは、本研究室で開発されている非破壊的木構造データベースである。 +Jungleは、プログラム内部に直接木構造を構築する。 +また、木の変更は、ルートをアトミックに入れ替えることでトランザクションを実現する。 +この方法により、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する。 +プログラムは、この木を内部のデータ構造として直接取り扱うことができる。 +また、汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。 +しかし、木構造の形によっては、木の変更の手間が大きくなる・Indexの更新処理が極めて重いという面があった。 + +本研究では、Jungleデータベースの大幅な改善を行い、既存のJungleとくらべて大幅な処理の高速化に成功した。 +また、Jungleを使用した例題アプリケーションを作成し、性能測定を行ったところ、木構造の形によって処理速度に差が出ることがわかった。 + \end{abstract} diff -r 90e06e17ca6b -r 6f9f9669b264 datebases.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/datebases.tex Sun Jan 29 11:57:18 2017 +0900 @@ -0,0 +1,32 @@ +\chapter{既存のデータベース} +本章では, まずデータベースの種類であるRelational DatabaseとNoSQL について述べる。 +次に、データベースに値を格納する際に、発生する問題であるインピータンスミスマッチについて触れる。 +最後に既存のデータベースである、○○○について述べる。 + +\section{Relational Database} +Relational Database(RDB)は、列と行からなる2次元のテーブルにより実装されるデータベースである。 +RDBが保持しているデータへのアクセスは、SQLを用いて行われる。 +テーブルに格納されるデータ型として、文字列・数値・日付・BOOL型があり、システムによりデータに型が強制される。 +RDBはスキーマの決まったデータを扱うことに長けている。 +また、既存のテーブルを結合することで、１つのテーブルとして扱うことが可能である。 +RDBの例として、MySQL・PostgreSQLなどがある。 + +\section{NoSQL} +NoSQLはNot Only SQLの略で、SQLを使わないデータベースのことを指す。 +NoSQLデータベースはRDBとは違いスキーマがない。 +そのため、扱おうとしているデータの形が決まっていなくても気軽に使うことができる。 +NoSQLの例として、MongoDB・Cassandra・当研究室で開発を行っているJungleなどがある。 + + +\section{インピータンスミスマッチ} +インピータンスミスマッチとは、プログラム中のデータ構造とRDBの表構造の間に生まれるギャップのことである。 +例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 +プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 +レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術では、これを本質的には解決することはできない。 +そこで、 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。 +しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 +並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、 +並列処理を含むプログラミングからの要請とのミスマッチが残っている。 + + + diff -r 90e06e17ca6b -r 6f9f9669b264 introduciton.tex --- a/introduciton.tex Sat Jan 28 19:28:01 2017 +0900 +++ b/introduciton.tex Sun Jan 29 11:57:18 2017 +0900 @@ -1,9 +1,29 @@ -\chapter{序論} +\chapter{研究目的} \pagenumbering{arabic} -序論を書く +プログラムからデータを分離して扱うデータベースには、 +プログラム中のデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。 +データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 +データベース自体も、表に特化したKey Value Store、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 +しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 + +そこで当研究室では、煩雑な設計を行わずプログラム内部に木構造を格納できるデータベースJungleを提案している。 +また、Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、 +木のルートをアトミックに入れ替えることでトランザクションを実現する。 +プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 +Jungleは分散構成も可能である。 + +Jungleは、様々の形の木構造を格納できるが、形によっては木の変更の手間が大きくなるなどの問題がある。 +そこで、本研究では、今までの汎用的な木ではなく、特定の形の木を格納することに特化した機能を実装した。 +また、Index等の木の編集時にネックとなっていた箇所にも改善を行った。 +その結果、木の更新速度を大幅に向上させることに成功した。 -\newpage - \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 章では、今回実装した機能の測定について記述する。 diff -r 90e06e17ca6b -r 6f9f9669b264 master_paper.tex --- a/master_paper.tex Sat Jan 28 19:28:01 2017 +0900 +++ b/master_paper.tex Sun Jan 29 11:57:18 2017 +0900 @@ -77,6 +77,7 @@ %chapters \input{introduciton.tex} +\input{datebases.tex} \input{jungle.tex} % Jungleの説明 \input{jungleUpdatePoint.tex} % 卒論との変更点 \input{redBlackTree.tex} diff -r 90e06e17ca6b -r 6f9f9669b264 redBlackJungleTree.tex --- a/redBlackJungleTree.tex Sat Jan 28 19:28:01 2017 +0900 +++ b/redBlackJungleTree.tex Sun Jan 29 11:57:18 2017 +0900 @@ -28,7 +28,7 @@ \begin{center} \caption{新たにJungle Tree Editorに定義したAPI} \begin{tabular}{|p{15em}|p{24em}|} \hline -{\tt Either addNewChildAndPutAttribute(NodePath path, int pos, String key, ByteBuffer value)} & pathで指定した位置にあるノードのpos番目に、属性名 keyと属性値 valueの組を持つノードを追加する。\\ \hline +{\tt Either addNewChildAndPutAttribute( NodePath path, int pos, String key, ByteBuffer value)} & pathで指定した位置にあるノードのpos番目に、属性名 keyと属性値 valueの組を持つノードを追加する。\\ \hline \end{tabular} \label{NewEditorAPI} \end{center} @@ -52,44 +52,54 @@ \end{center} \end{table} +\newpage Red Black Jungle Tree にノードを追加し、値を挿入するサンプルコードを記載する(ソースコード\ref{src:rbtEdit})。 \begin{lstlisting}[frame=lrbt,label=src:rbtEdit,caption=RedBlackJungleTreeの編集例,numbers=left] -String BalanceKey = "balanceKey"; -JungleTree tree = jungle.createNewRedBlackTree("TreeName", balanceKey); +String balanceKey = "balanceKey"; +JungleTree tree = jungle.createNewRedBlackTree("TreeName", balanceKey) JungleTreeEditor editor = tree.getJungleTreeEditor(); NodePath path = new RedBlackTreeNodePath(); ByteBuffer balanceValue = ByteBuffer.wrap(("Elphelt").getBytes()); Either either = editor.addNewChildAndPutAttribute(path, 0, balanceKey, balanceValue); -if (either.isA()) - return either.a(); +if (either.isA()) return either.a(); editor = either.b(); NodePath rbtPath = new RedBlackTreeNodePath(balanceKey,balanceValue)); String key = "key"; ByteBuffer value = ByteBuffer.wrap(("value").getBytes()) Either either = editor.putAttribute(rbtPath, key, testPutValue); -if (either.isA()) - return either.a(); +if (either.isA()) return either.a(); editor = either.b(); either = editor.success(); \end{lstlisting} +ソースコード\ref{src:rbtEdit}の解説を以下に記す。 +\begin{enumerate} +\item 木のバランスに使用するbalanceKeyを宣言する。 +\item 1で宣言したbalanceKeyを使って、Red Black Jungle Treeを{\tt TreeName}とい名前で作成する。 +\item 2で作成した木からEditorを取得する。 +\item 木の編集に使用するPathを作成する。 +\item 木にノードを値を挿入する際、属性名 balanceKeyとペアになる属性値 balanceValueを作成する。 +\item 木に1・5で作成した属性名 属性値のペアの値を持つノードを追加し、木のバランスを取る。 +\item 編集が成功したかを調べ、失敗していた場合エラーを返す。 +\item 成功していた場合{\tt either}から、編集後の木を持つEditorを取得する。 +\item 6で追加したノードを指し示すNodePathを作成する(属性名 balanceKey 属性値 balanceValueを持つノード)。 +\item ノードに追加する属性値 keyを宣言する。 +\item ノードに追加する属性名 valueを宣言する。 +\item 属性名 balanceKey 属性値 balanceValueを持つノードに、10・11で作成した属性名key 属性値 valueを追加する。 +\item 編集が成功したかを調べ、失敗していた場合エラーを返す +\item 成功していた場合{\tt either}から、編集後の木を持つEditorを取得する。 +\item 編集を木にCommitする。 +\end{enumerate} + + \section{Jungle Red Black Treeの検索} Red Black Jungle Treeへの検索は、Red Black Jungle Tree Traverserを用いて行う。 Red Black Jungle Treeは、Indexを持たないため、Traverser.find(Query query, String balanceKey, String balanceValue)の第二・第三引数は、木を作成する時に設定したbalanceKey・属性名 balanceKeyとペアのbalanceValueを取る。 -balanceKeyを使ったデータの検索は以下の手順で行う。 +初めに、balanceKeyとbalanceValueを使って、二分探索木の探索アルゴリズムを用いて条件に一致するノードを絞り込む。 +そして、絞り込んだノードが、Queryの条件と一致した場合、そのノードを返す。 +また、balanceKey以外の値を第二引数に渡した場合、検索は失敗する。 -\begin{enumerate} -\item 現在のノードから、findの第二引数で取得した、属性名 BalanceKeyとペアになっている属性値 valueを取得する。 -\item 1で取得した属性値 valueと、findの第三引数で取得したbalanceValueを比較する。 -\item 比較の結果、大きかった場合、右に、小さかった場合左のノードに進む。 -\item 同じ値を持つノードを発見するか、葉にたどり着くまで1~3を繰り返す。 -\item 同じ値を持つノードを発見したら、そのノードを返す。 -\item 葉までたどり着いた場合、その木は対応するノードを持っていないため -\item 5で取得したノードが、第一引数のqueryの条件に一致するか確かめる。 -\item 一致する場合そのノードを返す。 -\end{enumerate} - - -balanceKey・balanceValueを使用しない検索は、Default Jungle TreeのIndexを使わない検索と同じで、木の全探索を行う。 +balanceKey・balanceValueを引数に取らないTraverser.find(Query query)を使用する場合、Default Jungle TreeのIndexを使わない検索と同じで、木の全探索を行う。 +その際の探索オーダーはO(n)となる。 diff -r 90e06e17ca6b -r 6f9f9669b264 redBlackTree.tex --- a/redBlackTree.tex Sat Jan 28 19:28:01 2017 +0900 +++ b/redBlackTree.tex Sun Jan 29 11:57:18 2017 +0900 @@ -60,7 +60,7 @@ Red Black Treeのデータ挿入時のバランスは、次の5パターンに分けられる。 -\subsection{データ挿入時のバランス ケース1} +\section{データ挿入時のバランス ケース1} \begin{enumerate} \item ノードを挿入した位置がルート @@ -69,7 +69,7 @@ ルートノードの色を黒に変更しても、左右のSub Treeの黒の個数が一つ増えるだけなので、Red Black Treeの条件は守られる。 -\subsection{データ挿入時のバランス ケース2} +\section{データ挿入時のバランス ケース2} \begin{enumerate} \item 挿入したノードinsの親ノードBが黒。 \end{enumerate} @@ -84,7 +84,7 @@ %\end{center} %\end{figure} -\subsection{データ挿入時のバランス ケース3} +\section{データ挿入時のバランス ケース3} \begin{enumerate} \item 挿入したノードinsの親の親ノードAが黒。 \item ノードAの両方の子ノードB・Cが赤。 @@ -104,7 +104,7 @@ バランス後、ノードAを新しくノードinsとして再帰的に木のバランスを行う。 この変更は最悪の場合ルートまで続く。 -\subsection{データ挿入時のバランス ケース4} +\section{データ挿入時のバランス ケース4} \begin{enumerate} \item 挿入したノードinsの親の親ノードAが黒。 \item ノードAの、挿入したノード側の子ノードBが赤。 @@ -125,7 +125,7 @@ -\subsection{データ挿入時のバランス ケース5} +\section{データ挿入時のバランス ケース5} \begin{enumerate} \item 挿入したノードinsの親の親ノードAが黒。 \item ノードAの、挿入したノード側の子ノードBが赤。 @@ -165,14 +165,14 @@ また。これ以降削除対象のノードと置換したノードを、ノードrepと記述する。 -\subsection{データ削除時のバランス ケース1} +\section{データ削除時のバランス ケース1} \begin{enumerate} \item ノードrepがルート。 \end{enumerate} 上記の条件を満たしている場合、全ての経路の黒ノード数が1つ減った状態で条件が成立しバランスは終了する。 -\subsection{データ削除時のバランス ケース2} +\section{データ削除時のバランス ケース2} \begin{enumerate} \item ノードrepが黒。 \item ノードA・B・C・D・E・Fが黒。 @@ -192,7 +192,7 @@ \end{figure} -\subsection{データ削除時のバランス ケース3} +\section{データ削除時のバランス ケース3} \begin{enumerate} \item ノードrepが黒。 \item ノードA・C・D・E・Fが黒 @@ -211,7 +211,7 @@ \end{center} \end{figure} -\subsection{データ削除時のバランス ケース4} +\section{データ削除時のバランス ケース4} \begin{enumerate} \item ノードrepが黒。 \item ノードB・C・D・E・Fが黒 @@ -229,7 +229,7 @@ \end{figure} -\subsection{データ削除時のバランス ケース5} +\section{データ削除時のバランス ケース5} \begin{enumerate} \item ノードrepが黒。 \item ノードB・C・D・Fが黒。 @@ -248,7 +248,7 @@ \end{figure} -\subsection{データ削除時のバランス ケース6} +\section{データ削除時のバランス ケース6} \begin{enumerate} \item ノードrepが黒。 \item ノードB・C・Dが黒。