Mercurial > hg > Papers > 2017 > tatsuki-master

changeset 0:99d965c02c45

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit
author tatsuki
date Tue, 17 Jan 2017 18:47:09 +0900
parents
children da6a6eba893d
files chapter1.tex chapter2.tex chapter3.tex 修論.xmind
diffstat 4 files changed, 659 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/chapter1.tex	Tue Jan 17 18:47:09 2017 +0900
@@ -0,0 +1,435 @@
+\chapter{木構造データベースJungle}
+Jungleは、当研究室が開発を行っているデータベースで、Javaを用いて実装されている。
+Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。
+ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。
+通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
+Jungleでは、親から子への片方向の参照しか持たない。
+
+通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。
+この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。
+%特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、
+特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、
+十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。
+
+Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。
+Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
+持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では基本的に分散実装部分ではなく on memory DBの
+部分について考察する。
+本章ではまず破壊的木構造と、非破壊的木構造の説明をし、その後Jungleの提供しているAPIについて述べる。
+
+\subsection{破壊的木構造}
+破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。
+図\ref{fig:destractive}は破壊的木構造のにおけるデータ編集を表している。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
+    \caption{破壊的木構造の編集}
+    \label{fig:destractive}
+  \end{center}
+\end{figure}
+
+破壊的木構造は、編集を行う際に木のロックを掛ける必要がある。
+この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、閲覧者が
+いる場合は木の走査が終わるまで書き換えを待たなければならない。
+
+\subsection{非破壊的木構造}
+、データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。
+その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1 、3、 4は編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
+    \caption{非破壊的木構造の編集}
+    \label{fig:nondestractive}
+  \end{center}
+\end{figure}
+
+非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に
+ルートノードを更新するときだけである。
+データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが
+可能である。
+しかし、書き込み時の手間は大きくなる。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
+    \caption{非破壊的木構造による利点}
+    \label{fig:nondestractive_merit}
+  \end{center}
+\end{figure}
+
+\subsection{NodePath}
+Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。
+{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。また、ルートノードは例外として-1と表記される。
+{\tt NodePath}クラスが{\tt < -1,1,2,3>} を表している際の例を図\ref{NodePath}に記す。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.7]{figures/nodePath.pdf}
+\caption{NodePath}
+\label{NodePath}
+\end{center}
+\end{figure}
+
+
+\subsection{木の生成}
+初めにJungleにおける木の生成について述べる。
+Jungleは複数の木を、名前を利用して管理しており、名前を利用することで作成・編集・削除を行う。
+以下にJungleクラスが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。
+
+\begin{table}[htb]
+  \begin{center}
+  \caption{Jungleに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|}        \hline
+      {\tt JungleTree createNewTree(String treeName) } & Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。     \\ \hline
+      {\tt JungleTree getTreeByName(String treeName)}  & JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す       \\ \hline
+    \end{tabular}
+    \label{jungleAPI}
+  \end{center}
+\end{table}
+
+
+\subsection{JungleTree}
+Jungleは複数の木の集合で出来ている。
+ユーザーは、この木に対して検索や編集を行う。
+以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す
+\begin{table}[htb]
+\begin{center}
+\caption{JungleTreeに実装されているAPI}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+{\tt TreeNode getRootNode()} &木のルートノードを取得する。   \\ \hline
+{\tt long revision()} & 木のバーションを取得する。初めは0から始まり、木への変更がCommitされる度に1上昇する。 \\ \hline
+{\tt JungleTreeEditor getJungleTreeEditor()} & 木へ変更を加えるEditorを取得する。\\ \hline
+{\tt Either<Error, JungleTree> getOldTree(long revision)} & 引数で指定したrevisionの木を取得する。 \\ \hline
+{\tt InterfaceTraverser getTraverser()} & 木の検索を行うTraverserを取得する。 \\ \hline
+{\tt Either<Error, TreeNode> getNodeOfPath(NodePath path)} & {\tt NodePathで指定した位置値なるノードを取得する。}  \\ \hline
+{\tt NodePath getNodePath(TreeNode node)} & 引数で渡したノードの位置を表す{\tt NodePath}を返す。\\ \hline
+\end{tabular}
+\label{JungleTreeAPI}
+\end{center}
+\end{table}
+
+
+\subsection{Either}
+Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。
+AにはのErrorを、Bには処理に成功した際に入る値が入る。
+Eitherは、AかBどちらかの値しか持たない。
+以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。
+\begin{table}[htb]
+\begin{center}
+\caption{Eitherに実装されているAPI}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+{\tt boolean isA()} & EitherがAを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
+{\tt boolean isB()} & EitherがBを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
+{\tt A a()} Aの値を取得する。& \\ \hline
+{\tt B b()} Bの値を取得する。& \\ \hline
+\end{tabular}
+\label{EitherAPI}
+\end{center}
+\end{table}
+
+{\tt Either<A、B>}は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。
+{\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。
+
+
+\subsection{TreeNode}
+Jungleが保持している木は、複数のノードの集合で出来ている。
+ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
+ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。
+
+\begin{table}[htb]
+  \begin{center}
+    \caption{TreeNodeに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
+      {\tt Children getChildren()} & ノードの子供を扱うChildrenオブジェクトを返す。\\ \hline
+      {\tt Attribute getAttribute()} &ノードが保持しているデータを扱うAttribteオブジェクトを返す。    \\ \hline
+    \end{tabular}
+    \label{TreeNodeAPI}
+  \end{center}
+\end{table}
+
+Childrenクラスは表\ref{Children}に記述されたAPIを、Attributeクラスは表\ref{Attribute}に記述されたAPIを提供する。
+これらを利用しノードの子供や、保持する値にアクセスする。
+\begin{table}[htbH]
+  \begin{center}
+    \caption{Childrenに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
+      {\tt int size()}  &  子供の数を返す。\\ \hline
+      {\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。   \\ \hline
+    \end{tabular}
+  \label{Children}
+  \end{center}
+\end{table}
+
+
+関数{\tt children.at(int num)}が返す{\tt Either\textless Error,TreeNode\textgreater} オブジェクトは、{\tt isA() }で{\tt Error}かどうかをチェックすることができる。
+{\tt Error}でない場合は{\tt b()}で{\tt TreeNode}オブジェクトを取り出すことができる。
+
+
+
+
+\begin{table}[htbH]
+  \begin{center}
+    \caption{Attributeに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|} \hline
+      {\tt ByteBuffer get(String key)}   &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。 \\ \hline
+      {\tt String getString(String key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。 \\ \hline
+    \end{tabular}
+  \label{Attribute}
+  \end{center}
+\end{table}
+
+\newpage
+以下にルートノードの2番目の子供から、属性名 {\tt name}とペアになっている属性値を取得するサンプルコードを記述する。
+\begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
+JungleTree tree = jungle.getTreeByName("TreeName");
+TreeNode root = tree.getRootNode();
+Children children = root.getChildren();
+Either<Error,TreeNode> either = children.at(2);
+if (either.isA()) 
+  throw new IOException();
+TreeNode child = either.b();
+Attribute attribute = child.getAttribute();
+String value = attribute.getString("name");
+\end{lstlisting}
+
+\begin{enumerate}
+  \item Jungleから名前を指定して木を取得する。 
+  \item 取得した木のルートノードを取得する。
+  \item 木のルートノードから{\tt Children}型の子ノードを取得する。
+  \item 変数{\tt children}から2番目の子供を取得する。
+  \item 2番目の子供が取得できたかを調べる。
+  \item 取得できていなかった場合{\tt Exception}を投げる。
+  \item 取得に成功していた場合、{\tt either}から子ノードを受け取る。
+  \item 取得した子ノードから{\tt Attribute}クラスを取得する。
+  \item 取得した{\tt attribute}から属性名 {\tt name}がペアの値を取得する。
+\end{enumerate}
+
+\subsection{木の編集API}
+Jungleの木の編集は{\tt JungleTreeEditor}クラスを用いて行われる。
+{\tt JungleTreeEditor}クラスには編集を行うために、表\ref{editor}で定義されているAPIが実装されている。
+
+\begin{table}[htb]
+  \begin{center}
+    \caption{Editorに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|}        \hline
+      {\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path,  int pos)} &
+      変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置子ノードを追加する\\ \hline
+      {\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path,int pos)}      &
+      変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline
+      {\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path,String key,ByteBuffer value)} &
+      変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline
+      {\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path,String key)}&
+      変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されているデータを削除する。\\ \hline
+      {\tt Either<Error, JungleTreeEditor> moveChild( NodePath path,int num,String move)} &
+      変数{\tt path}で指定した場所にある、ノードの変数{\tt num}で指定された位置の子供を変数{\tt move}の方向に移動させる。 \\ \hline
+      {\tt Either<Error, JungleTreeEditor> pushPop()} &
+      ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで計算量をO(n)からO(1)にできる。\\ \hline
+      {\tt Either<Error, JungleTreeEditor> success()}  &
+      木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
+    \end{tabular}
+  \label{editor}
+  \end{center}
+\end{table}
+
+
+
+編集後に返される{\tt JungleTreeEditor}クラスは、編集後の木構造を保持しているため、編集前の木構造を保持している{\tt JungleTreeEditor}クラスとは別のオブジェクトである。
+編集を行った後は、関数{\tt editor.success()}で今までの編集をコミットすることができる。他の{\tt JungleTreeEditor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。
+その場合は、木の編集を最初からやり直す必要がある。
+
+以下に{\tt JungleTreeEditor}クラスを用いて、木の編集を行うサンプルコードを記述する。
+
+\begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
+JungleTreeEditor editor = tree.getTreeEditor();
+DefaultNodePath editNodePath = new DefaultNodePath();
+Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0);
+if (either.isA()) 
+  throw new IllegalStateException();
+editor = either.b();
+editor.success();
+\end{lstlisting}
+
+\begin{enumerate}
+  \item 関数{\tt tree.getEditor()}で編集を行う木から、{\tt JungleTreeEditor}クラスを取得する。 
+  \item 次に変更するノードの場所を示す、{\tt NodePath}クラスを作成する。
+  \item 関数{\tt editor.addNewChildAt()}を用いて、変数{\tt path}で指定したノードの子供の0番目に子ノードを追加する。
+  \item 返り値の変数{\tt either}が{\tt Error}クラスを保持していないか(編集に失敗していないか)を確認する。
+  \item {\tt Error}クラスを保持していた場合{\tt Exception}を投げる。
+  \item 編集に成功していた場合、編集後木を持った、{\tt JungleTreeEditor}クラスを取得する。
+  \item 取得した{\tt JungleTreeEditor}クラスを用いて木の変更をコミットする。
+\end{enumerate}
+
+また、木に対して行われた変更は、Logとして書き出される。
+これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。
+
+
+\subsection{検索APIの実装}
+これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。
+しかし、木に問い合わせを行う検索APIが実装されていなかったため、属性名 {\tt key} 属性値 {\tt value}の組で検索を行うAPIの実装を、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて行った。
+以下に検索を行う関数{\tt find}の定義を記述する。
+\begin{lstlisting}[frame=lrbt,label=query,numbers=left]
+public Iterator<TreeNode> find(Query query, 
+               String key, String searchValue);
+\end{lstlisting}
+関数{\tt find}は引数に、{\tt Query query}、{\tt String key}、{\tt String value}の3つの引数を取り、条件に一致したノードの{\tt Iterator}インタフェースを返す。
+第1引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Interface Query}を。
+第2、第3引数の、{\tt String key、String value}はIndexを用いた絞込みに使用する。{\tt 関数find}の使用例を以下に記す
+
+\begin{lstlisting}[frame=lrbt,label=find,numbers=left]
+InterfaceTraverser traverser = tree.getTraverser(true);
+Iterator<TreeNode> resultNodeIterator = traverser.find((TreeNode node) -> {
+    String personId = node.getAttributes().getString("name");
+      if (personId == null) return false;
+        return personId.equals("kanagawa");
+}, "belong", "ryukyu");
+\end{lstlisting}
+
+
+上記コードについて解説する。
+\begin{enumerate}
+  \item 木の走査を行う{\tt Traverser}クラスを取得する。
+
+  \item Indexから{\tt find}の第2、第3引数である、属性名 {\tt belong}、属性値 {\tt ryukyu}の組のデータを持つノードを取得し、Queryに渡す(ノードの絞込を行う)。
+
+  \item 引数のノードから関数{\tt getAttributes().getString("name")}で属性名 {\tt name}とペアになっている属性値を取得する。
+  
+  \item 属性値が{\tt null}だった場合、このノードには属性名が{\tt name}の組のデータは存在しないので、{\tt false}を返し次のノードの評価を行う。
+
+  \item 属性値が{\tt null}でなかった場合、{\tt kanagawa}と一致するかどうかを調べ結果を返す。
+
+\end{enumerate}
+
+このコードの結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータが入ったノードが取得できる。
+
+
+\subsection{Indexの実装}
+Jungleには、検索の際に使用するIndexが無かったため、実装を行った。
+Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持しているため、全ての版に独立したIndexが必要となる。
+そのため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。
+既存のTreeMapでは、一度Indexの複製を行った後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。
+よって、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。
+このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。
+Jungleとの違いは、木の回転処理が入ることである。
+これにより複数の版全てに対応したIndexをサポートすることが可能になった。
+以下にJungleにおけるIndexの型を記述する
+
+\begin{lstlisting}[frame=lrbt,label=index,numbers=left]
+TreeMap<String key,TreeMap<String attribute,
+  List<TreeNode> node> index> indexMap
+\end{lstlisting}
+
+JungleのIndexは{\tt IndexMap}内に保持されている。
+属性名で{\tt IndexMap}に{\tt get}を行うと、対応したIndexが取得できる。
+取得したIndexに属性値で{\tt get}を行うと、ノードのリストが返ってくる。
+以下にIndexから属性名 name 属性値 kanagawaのデータを持つ、ノードのIteratorを取得するサンプルコードを記述する。
+
+\begin{lstlisting}[frame=lrbt,label=find,numbers=left]
+Optional<TreeMap<String, List<TreeNode>>> indexOp = indexMap.get("name");
+if (!indexOp.isPresent())
+  return new NulIterator<TreeNode>();
+TreeMap<String, List<TreeNode>> index = indexOp.get();
+Optional<List<TreeNode>> nodeListOp = index.get("kanagawa");
+if (!nodeListOp.isPresent())
+  return new NulIterator<TreeNode>();
+return nodeListOp.get().iterator();
+\end{lstlisting}
+
+
+\begin{enumerate}
+\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt name}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。
+
+\item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexをJungleが持っているか)を調べる。
+
+\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
+
+\item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。
+
+\item 取得したIndexに、検索で使用する属性値{\tt kanagawa}で{\tt get()}を行う。属性名 {\tt name} 属性値{\tt  kanagawa}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。
+
+\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt name} 属性値 {\tt kanagawa}を持つノードをJungleが持っているか)を調べる。
+
+\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
+
+\item 持っていた場合{\tt Optional}オブジェクトからノードリストの{\tt Iterator}を返す。
+
+\end{enumerate}
+
+\subsection{Log}
+
+JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。
+
+
+\begin{comment}
+\subsection{NodeOperation}
+Jungle による最小のデータ編集は Node の編集を指す.
+Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる.
+NodeOperation には次の4つの API が用意されている.
+\begin{itemize}
+\item \verb|addNewChild(NodePath _path, int _pos)|\\
+    NodePath で指定された Node に子供となる Node を追加する API である.
+    pos で指定された番号に子供として追加を行う.
+    \item \verb|deleteChildAt(NodePath _path, int _pos)|\\
+      NodePath と pos により指定される Node を削除する API である.
+      \item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|\\
+        Node に attribute を追加する API である. 
+        NodePath は attribute を追加する Node を指す.
+        \item \verb|deleteAttribute(NodePath _path, String _key)|\\
+          \verb|_key| が示す attribute の削除を行う API である.
+          NodePath は Node を示す.
+          \end{itemize}
+
+          NodeOperationはNodePathとセットで扱わなければならず, このセットを
+          TreeOperationという.
+          TreeOperationが1つのデータ編集の単位になるが, これはあくまで最小のデータ編集の単位である.
+          Jungle によるデータの編集はTreeOperationが複数集まった単位でcommitされていく.
+          このTreeOperationの集まりをTreeOperationLogという.
+
+          \subsection{TreeOperationLog}
+          Jungle 内部ではTreeOperationは順次ログに積まれていき, 最終的に
+          commitされることで編集が完了する.
+          この時, ログに積まれた複数のTreeOperationはTreeOperationLogとして扱われる.
+          TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す.
+          \begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
+          public interface TreeOperationLog extends Iterable<TreeOperation>
+{
+  public TreeOperationLog add(NodePath _p,NodeOperation _op);
+  public TreeOperationLog append(TreeOperationLog _log);
+  public int length();
+}
+\end{lstlisting}
+　\verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている.
+addやappendメソッドを使ってTreeOperationを積み上げていくことができる.
+
+次にデータ編集により発生するTreeOperationLogの具体的な例を示す(ソースコード\ref{src:treelog}).
+\begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
+[APPEND_CHILD:<-1>:pos:0]
+[PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
+[PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]
+[PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0]
+\end{lstlisting}
+　このログはルートノードに対し子ノードを追加し, 追加した子ノードに attribute を3つ追加する際に出力されるログである(図\ref{fig:treeoperationlog}).
+
+大文字の英字は実行した NodeOperation の種類を表す.
+\verb|<>| により囲まれている数字は NodePath を示す.
+NodePath の表記以降は Node の position や attribute の情報を表している.
+
+\newpage
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.7]{figures/treeoperationlog1.pdf}
+\caption{TreeOperationLog の具体例}
+\label{fig:treeoperationlog}
+\end{center}
+\end{figure}
+
+ログの動作を表している図\ref{fig:treeoperationlog}の説明を行う.
+まず, \verb|APPEND_CHILD:<-1>:pos:0|によりRoot Nodeの0番目の子供となるNodeの追加を行う.
+次に, 追加を行ったNodeに対して\verb|PUT_ATTRIBUTE<-1,0>| により attribute の情報を持たせていく.
+attributeの内容に作者の情報を表すauther, メッセージの内容を表すmes, そしてタイムスタンプ
+をtimestampとそれぞれキーにすることで追加される.
+
+以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である.
+\end{comment}
+\newpage
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/chapter2.tex	Tue Jan 17 18:47:09 2017 +0900
@@ -0,0 +1,173 @@
+\chapter{Differential Tree}
+前章でも述べたが、Jungleの木の変更の手間は木の形によって異なる。
+特に線形の木を構築した場合は変更の手間がO(n)となってしまう。
+Jungleは、線形の木をO(1)で変更するために、ルートノードを追加していくPushPopの機能を持つ。
+しかし、PushPopではルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまう。
+ノードを正順で線形の木を構築する際は、PushPopを使用できないため、O(n)で木の編集を行う必要がある。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.5]{figures/PushPopDemerit.pdf}
+\caption{PushPopの問題点}
+\label{fig:pushpop}
+\end{center}
+\end{figure}
+
+その問題を解決するために、木の編集の手間をO(1)で、正順の木を構築するDifferential Treeの実装を行った。
+本章ではDifferential Treeについて述べる。
+
+\newpage
+\section{Differential Treeの設計}
+Jungleの木は、過去の木を全て保持している必要があるため、過去の木を破壊することなく編集する必要がある。
+しかし、編集したノードからルートまでの複製を行うと、木の変更の手間はO(n)になってしまう。
+よって、木の複製を行わず過去の木を破壊することなく、木の編集を行う必要がある。
+Differential Treeでは、末尾ノードを使用することで、O(1)での木の編集を可能にした。
+
+Jungleの木はTreeContextというオブジェクトに自身の木の情報を保持する。 
+表\ref{TreeContext}にTreeContextが保持するデータを記述する。
+\begin{table}[htb]
+\begin{center}
+\caption{TreeContextが保持している値}
+\begin{tabular}{|l|}        \hline
+{\tt } 自身のルートノード\\ \hline
+{\tt } 1つ前のversionのTreeContext\\ \hline
+{\tt } 編集のログ\\ \hline
+{\tt } 木のuuid    \\ \hline
+{\tt } 木の名前    \\ \hline
+{\tt } 木のversion    \\ \hline
+{\tt } 木の検索に使うTraverser    \\ \hline
+\end{tabular}           
+\label{TreeContext}
+\end{center}                  
+\end{table}  
+
+TreeContextに、木の末尾ノードを追加したDifferential Tree Contextの実装を行うことで、Differential Treeに末尾ノードを保持させた。
+
+
+\section{末尾ノードを使用した木の編集}
+Differential Treeの木の編集は、Default Treeと同じようにEditorを使用して行う。
+Default Treeとの違いは、Default TreeのEditorは、木の編集を行った後、木の複製を行い過去の木を保持するのに対して、Differential TreeのEditorは、Sub Treeを保持しており、そのSub Treeに対して破壊的に編集を行う。
+そして、Commitを行う際に、構築したSub Treeを末尾ノードにAppendすることで木の編集を行う。
+そうすることで、木の複製を行う必要が無いため、木の変更の手間はO(1)で行える。
+また、Differential TreeはSub Treeに対する変更しか行えないため、一度Commitした木に対して変更は行えない。
+図\ref{fig:EditDifTree}にDifferential Treeの編集の流れを記述する。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.28]{figures/EditDifferencialTree.pdf}
+\caption{末尾ノードを使用した木の編集}
+\label{fig:EditDifTree}
+\end{center}
+\end{figure}
+
+\newpage
+\begin{enumerate}
+\item  木から{\tt getTreeEditor}でEditorを取得する。(このとき取得するEditorはSub Treeを持つ)
+\item  SubTreeに対して{\tt addNewChild(<-1,0>)}を実行し、ノードの追加を行う。
+\item  Commitを行い、Treeの末尾ノードにSub TreeをAppendする。
+\end{enumerate}
+
+また、Differential TreeのIndexのアップデートは、Sub Treeの中身をIndexに追加するだけで良い。
+
+\section{Commit Operation}
+Default Treeでは、木に対しての変更は、全てメインの木に対する変更であるため、Logに書き出された全ての変更を一回のCommitで行える。
+しかし、Differential Treeの変更は、Editorが保持しているsubTreeに対する変更であるため、適切なタイミングでCommitを行わないと、実際に行われた変更とズレが生じて、正しい木を構築できない。
+
+以下に、Logからの木の構築をする際に、一回のCommitでは適切なDifferential Treeを構築できない例を記す。
+\begin{lstlisting}[frame=lrbt,label=src:treelog,caption=適切な木を構築できないLogの例,numbers=left]
+1.[APPEND_CHILD:<-1>:pos:0]
+2[COMMIT]
+3.[APPEND_CHILD:<-1>:pos:0]
+4.[APPEND_CHILD:<-1,0>:pos:0]
+\end{lstlisting}
+
+大文字の英字はLogとして書き出された Operation の種類を表す。
+\verb|<>| により囲まれている数字は NodePath を示す。
+NodePath の表記以降は、ノードの position などの情報を表している。
+[COMMIT]は、実際の木を構築した際にCommitが行われたタイミングを表す。
+
+[COMMIT]のタイミングでCommitを行わず、全ての変更を加えた後にCommitを行った場合、図\ref{fig:badDifTreeCreate}のような変更が加えられ、図\ref{fig:badDifTree}のような木が構築される。
+しかし、実際には、図\ref{fig:createGoodDifTree1}、図\ref{fig:createGoodDifTree2}のような変更が加えられ、図\ref{fig:goodDifTree}のような木が構築されている。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.5]{figures/badDifTreeCreate.pdf}
+\caption{適切なタイミングでCommitを行わない木の復元の流れ}
+\label{fig:badDifTreeCreate}
+\end{center}
+\end{figure}
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.5]{figures/BadDifTree.pdf}
+\caption{適切なタイミングでCommitを行わなかった木}
+\label{fig:badDifTree}
+\end{center}
+\end{figure}
+
+\newpage
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/goodDifTreeCreate1.pdf}
+\caption{適切なタイミングでCommitを行なう、木の復元の流れ(1回目のCommit前)}
+\label{fig:createGoodDifTree1}
+\end{center}
+\end{figure}
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/goodDifTreeCreate2.pdf}
+\caption{適切なタイミングでCommitを行なう、木の復元の流れ(2回目のCommit前)}
+\label{fig:createGoodDifTree2}
+\end{center}
+\end{figure}
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.5]{figures/goodDifTree.pdf}
+\caption{適切なタイミングでCommitを行なった木}
+\label{fig:goodDifTree}
+\end{center}
+\end{figure}
+
+\newpage
+Logとして書き出されたTreeOperationから、適切な構造のDifferential Treeを構築するためには適切なタイミングでCommitを行う必要がある。
+この問題を解決するために、CommitのタイミングをLogとして書き出し、適切なタイミングでCommitを行えるようにした。
+
+
+\section{末尾ノードへのAppendの整合性}
+JungleのTreeは、過去の木を全て保持している。
+Differential Treeは、木を破壊的に変更するため、過去の木に変更を加えた場合木の整合性が崩れてしまうため、過去の木への編集を禁止する必要がある。
+ソースコード\ref{src:Append}にSub TreeのAppend部分のコードを記述する。
+
+\begin{lstlisting}[frame=lrbt,label=src:Append,caption=Sub TreeのAppend部分のコード,numbers=left]
+Either<Error, TreeNode> appendSubTree(TreeNode subTreeRoot) {
+  TreeNode appendedNode = treeContext.getEndNode();
+  TreeNodeChildren children = appendedNode.getChildren();
+  if (children.size() != 0)
+    return DefaultEither.newA(APPEND_FAILD); 
+  return children.addNewChildAt(0, subTreeRoot);
+}
+\end{lstlisting}
+以下にソースコード\ref{src:Append}の解説を行う。
+\begin{enumerate}
+\item 関数{\tt appendSubTree}でSub TreeのAppendを行う。引数にSub Treeのルートを持つ。 
+\item TreeContextから末尾ノードを取得する。
+\item 末尾ノードからChildrenを取得する。
+\item 末尾ノードにSub TreeがすでにAppendされているか(子供を持っているか)を調べる。
+\item 他のSub TreeがAppendされている(今編集を行っているのが過去の木)場合、木のAppendは失敗するため、エラーを返す。
+\item そうでない場合、Sub Treeを末尾ノードにAppendする。
+\end{enumerate}
+
+このように、過去の木への編集を禁止することで、木の整合性を保証している。
+
+
+\section{Differential Treeの検索}
+Differential Treeは、木を破壊的に編集する。
+そのため、過去の木から特定の値を持ったノードを取得する際、全てのノードを走破した場合その版の木には無いはずのノードが取得できてしまうことがある。
+そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から取り除く、検索を実装した。
+
+Indexを使用した検索を行う場合、各版に対応したIndexがあるため、Default Treeと検索の方法は変わらない。
+
+これらの機能を実装したことにより、Differential Treeは完成した。
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/chapter3.tex	Tue Jan 17 18:47:09 2017 +0900
@@ -0,0 +1,51 @@
+\chapter{Red Black Jungle Tree}
+Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。
+Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を構築できる。
+そこで、ノードの挿入を行うと木のバランスを取る、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。
+
+\section{Red Black Tree}
+初めにRed Black Treeの説明を行う。
+
+Red Black Treeは二分探索木の一つで、以下の条件を満たした木のことである。
+
+\begin{enumerate}
+\item ノードは赤か黒の色を持つ。 
+\item ルートノードは黒ノード。
+\item 全ての葉は黒である(空の黒ノードを持つ)。
+\item 赤いノードの子は黒である。
+\item 全ての葉からルートまでのパスには、同じ個数の黒いノードがある。
+\end{enumerate}
+
+赤黒木は、データの挿入、削除時に、上記の条件を崩さないように木のバランスを取る。
+
+この条件により、赤黒木はデータの検索、削除、探索をO(log n)で行える。
+
+
+\section{Red Black Treeへのデータの挿入}
+Red Black Treeへのデータの挿入は、以下の手順で行われる。
+
+\begin{enumerate}
+\item 挿入を行うノードと、現在のノードを比較する。
+\item 比較の結果、挿入を行うノードが現在のノードより大きかった場合、右に、小さかった場合左のノードに進む。
+\item 挿入を行う場所にたどり着くまで、１・２を繰り返す。
+\item 現在の位置に、赤色でノードを挿入する。
+\end{enumerate}
+
+挿入を行った後は、Red Black Treeの条件を崩さないように、木のバランスを取る。
+
+Red Black Treeのデータ挿入時のバランスは次の4パターンに分けられる。
+
+\subsection{Red Black Treeへのデータ挿入時のバランス 1}
+ノードを挿入した位置がルートだった場合、無条件でノードの色を黒に変更できる。
+ルートノードの色が黒になっても左右のSub Treeの黒の個数が一つ増えるだけなので、Red Black Treeの条件は守られる。
+
+また、親が黒色の場合、Red Black Treeの条件は崩れないため、そのまま赤色でノードを挿入して問題はない(図\ref{fig:RedBlackTreeInsert1})。
+
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.7]{figures/destructive_tree.pdf}
+\caption{Red Black Treeへのデータ挿入時のバランス1}
+\label{fig:RedBlackTreeInsert1}
+\end{center}
+\end{figure}
Binary file 修論.xmind has changed