\chapter{木構造データベースJungleの分散設計}
\section{木構造データベースJungle}
Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.

ここではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる.
\subsection{破壊的木構造}
破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
図\ref{fig:destractive}は破壊的木構造の編集を表している.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.8]{figures/destructive_tree.pdf}
    \caption{破壊的木構造の編集}
    \label{fig:destractive}
  \end{center}
\end{figure}

破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある.
この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
いる場合は木の走査が終わるまで書き換えをまたなければならない.
これではロックによりスケーラビリティが損なわれてしまう.

\subsection{非破壊的木構造}
非破壊的木構造は破壊的木構造とは違い, 一度作成した木を破壊することはない.
非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを
行い新しく木構造を作成することで行われる.
図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
    \caption{非破壊的木構造の編集}
    \label{fig:nondestractive}
  \end{center}
\end{figure}

非破壊的木構造におけるデータ編集の手順を以下に示す.

\begin{enumerate}
\item ルートから編集を行うノードまでのパスを調べる(図\ref{fig:nondestractive_edit1}).
\item 編集を行うノードのコピーをとる. コピーをとったノードへデータの編集を行う(図\ref{fig:nondestractive_edit2}).
\item 調べたパスに従いルートからコピーしたノードまでの間のノードのコピーをとり繋げる(図\ref{fig:nondestractive_edit3}).
\item コピーしたルートノードは編集を行っていないノードへの参照を貼り新しい木構造を作る(図\ref{fig:nondestractive_edit4}).
\end{enumerate}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf}
    \caption{非破壊的木構造の編集1}
    \label{fig:nondestractive_edit1}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf}
    \caption{非破壊的木構造の編集2}
    \label{fig:nondestractive_edit2}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf}
    \caption{非破壊的木構造の編集3}
    \label{fig:nondestractive_edit3}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf}
    \caption{非破壊的木構造の編集4}
    \label{fig:nondestractive_edit4}
  \end{center}
\end{figure}

非破壊的木構造により, 木構造を編集しながら走査することが可能となる.

\section{Jungleの分散データベース設計}