# HG changeset patch # User matac42 # Date 1681720339 -32400 # Node ID efdfdb9979846b5ec5d6e4836b115580586e4050 # Parent b2ecc555e86e01d81302ced3549c7573e1cc9982 ... diff -r b2ecc555e86e -r efdfdb997984 Paper/figs/backup.drawio diff -r b2ecc555e86e -r efdfdb997984 Paper/figs/read.drawio --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/figs/read.drawio Mon Apr 17 17:32:19 2023 +0900 @@ -0,0 +1,124 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + \ No newline at end of file diff -r b2ecc555e86e -r efdfdb997984 Paper/figs/transaction.drawio --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/figs/transaction.drawio Mon Apr 17 17:32:19 2023 +0900 @@ -0,0 +1,104 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r b2ecc555e86e -r efdfdb997984 Paper/figs/transaction.drawio.pdf Binary file Paper/figs/transaction.drawio.pdf has changed diff -r b2ecc555e86e -r efdfdb997984 Paper/figs/transaction.png Binary file Paper/figs/transaction.png has changed diff -r b2ecc555e86e -r efdfdb997984 Paper/figs/transaction.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/figs/transaction.svg Mon Apr 17 17:32:19 2023 +0900 @@ -0,0 +1,1 @@ + \ No newline at end of file diff -r b2ecc555e86e -r efdfdb997984 Paper/paper.aux --- a/Paper/paper.aux Mon Apr 17 11:20:40 2023 +0900 +++ b/Paper/paper.aux Mon Apr 17 17:32:19 2023 +0900 @@ -25,9 +25,9 @@ \@writefile{toc}{\contentsline {section}{\numberline {5}\hskip 1zw{ディスク上とメモリ上のデータ構造}}{3}{}\protected@file@percent } \@writefile{toc}{\contentsline {section}{\numberline {6}\hskip 1zw{データのロールバックとバックアップ}}{3}{}\protected@file@percent } \@writefile{toc}{\contentsline {section}{\numberline {7}\hskip 1zw{RedBlackTreeのトランザクション}}{4}{}\protected@file@percent } +\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces トランザクショナルなwrite時のルート操作\relax }}{4}{}\protected@file@percent } +\newlabel{fig:Transaction}{{5}{4}} \@writefile{toc}{\contentsline {section}{\numberline {8}\hskip 1zw{ファイルシステムにおけるスキーマ}}{4}{}\protected@file@percent } -\@writefile{toc}{\contentsline {section}{\numberline {9}\hskip 1zw{RedBlackTreeによる権限の表現}}{4}{}\protected@file@percent } -\@writefile{toc}{\contentsline {section}{\numberline {10}\hskip 1zw{まとめと今後の課題}}{4}{}\protected@file@percent } \citation{*} \bibstyle{ipsjunsrt} \bibdata{matac-bib} @@ -44,6 +44,8 @@ \bibcite{xv6component}{11} \bibcite{xv6}{12} \bibcite{christie}{13} +\@writefile{toc}{\contentsline {section}{\numberline {9}\hskip 1zw{RedBlackTreeによる権限の表現}}{5}{}\protected@file@percent } +\@writefile{toc}{\contentsline {section}{\numberline {10}\hskip 1zw{まとめと今後の課題}}{5}{}\protected@file@percent } \@writefile{toc}{\contentsline {subsection}{\numberline {10.1}{データクエリ言語}}{5}{}\protected@file@percent } \@writefile{toc}{\contentsline {subsection}{\numberline {10.2}{ログなどの時系列データの保存}}{5}{}\protected@file@percent } \@writefile{toc}{\contentsline {subsection}{\numberline {10.3}{スタンドアロンなDB}}{5}{}\protected@file@percent } diff -r b2ecc555e86e -r efdfdb997984 Paper/paper.log --- a/Paper/paper.log Mon Apr 17 11:20:40 2023 +0900 +++ b/Paper/paper.log Mon Apr 17 17:32:19 2023 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.141592653-p4.0.0-220214-2.6 (utf8.euc) (TeX Live 2022) (preloaded format=platex 2022.6.9) 17 APR 2023 11:19 +This is e-pTeX, Version 3.141592653-p4.0.0-220214-2.6 (utf8.euc) (TeX Live 2022) (preloaded format=platex 2022.6.9) 17 APR 2023 17:29 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -3200,11 +3200,14 @@ [2] File: figs/nonDestroyTreeEdit.pdf Graphic file (type pdf) - [3] [4] + [3] +File: figs/transaction.drawio.pdf Graphic file (type pdf) + + [4] LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <9.61035> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 378. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 394. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <9.61035> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 378. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 394. (./paper.bbl LaTeX Font Info: Calculating math sizes for size <8.8711> on input line 1. @@ -3233,12 +3236,12 @@ ) Here is how much of TeX's memory you used: - 5097 strings out of 478724 - 81242 string characters out of 5858393 + 5103 strings out of 478724 + 81414 string characters out of 5858393 627481 words of memory out of 5000000 - 23499 multiletter control sequences out of 15000+600000 + 23504 multiletter control sequences out of 15000+600000 499135 words of font info for 160 fonts, out of 8000000 for 9000 929 hyphenation exceptions out of 8191 - 55i,10n,63p,294b,1365s stack positions out of 10000i,1000n,20000p,200000b,200000s - -Output written on paper.dvi (5 pages, 41760 bytes). + 55i,11n,63p,294b,1365s stack positions out of 10000i,1000n,20000p,200000b,200000s + +Output written on paper.dvi (5 pages, 42996 bytes). diff -r b2ecc555e86e -r efdfdb997984 Paper/paper.pdf Binary file Paper/paper.pdf has changed diff -r b2ecc555e86e -r efdfdb997984 Paper/paper.synctex.gz Binary file Paper/paper.synctex.gz has changed diff -r b2ecc555e86e -r efdfdb997984 Paper/paper.tex --- a/Paper/paper.tex Mon Apr 17 11:20:40 2023 +0900 +++ b/Paper/paper.tex Mon Apr 17 17:32:19 2023 +0900 @@ -322,6 +322,22 @@ それによって，RedBlackTreeは複数の書き込みポイントを持つことができ， writeを並行実行することが可能となる． +図\ref{fig:Transaction}にトランザクショナルなwrite時のルート操作を表す． +Aの木はファイルシステム全体を表すRedBlackTreeである． +ノードNのデータに対して書き込みすることを考える． +キーがaであるBの木のルートからロックしCの木を作成して， +Bの木からCの木のルートに入れ替えることで書き込みを行う． +この書き込みを行っている際， +Aの木のノードはロックしないのでAの木のどのノードに対しても並行して書き込み可能となる． + +\begin{figure}[ht] + \begin{center} + \includegraphics[width=80mm]{figs/transaction.drawio.pdf} + \end{center} + \caption{トランザクショナルなwrite時のルート操作} + \label{fig:Transaction} +\end{figure} + % TODO: read時常に最新の情報が取れないことを説明する図を入れたい readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である．