nitpick 『詳説データベース』

CRDTなデータベースをon-diskで実装してえ…という思いが高まってきたので購入。ストレージエンジンと分散システムというトピックはどっちも興味があるのですごい嬉しいしオライリーだからDRMフリーPDFなのも素晴らしい。
ただ、読んでて筆が滑ったのか自分の読み方が良くないだけなのか不明なところがちょくちょくあるのでメモしたいと思う。ただ、この記事はnitpickであって内容の良しあしとは関係ないのでそこは注意すること。
「ここはこういう意味だよ！」とか「普通に読めるよ！」とかコメントいただけると幸いです。

Bツリーの本質はノード内の二分探索ではない (2.3 ユビキタスBツリー)

曰く、

Bツリーはソートされています。つまり、Bツリーのノード内のキーは、順番に格納されています。それゆえに、検索対象のキーを探すために二分探索のようなアルゴリズムが使用できます。このことは、Bツリーにおける検索は対数オーダーの計算量に従うことも意味します。（太字筆者）

この文章では、Bツリーのノード内で二分探索できることがBツリーの検索の計算量オーダーに効いていると読めると思う*1。
しかし、この因果関係の読みは正しくない。なぜならば、Bツリーがもたらす対数オーダーはノード間に構成された完全な木の高さが全要素数の対数に比例することに由来しているからであって、ノード内での探索が二分探索だろうが線型探索であろうが関係は無い。
このことはノードのスプリットやマージを考えると分かりやすいと思う。スプリットやマージではノード内の要素を半分移す必要があるから、それぞれのノードについてノード内の要素数に比例するオーダーの計算量がかかる。
けれども、一回の挿入や削除に伴うスプリットやマージの回数が木の高さ、すなわち全要素数の対数、に抑えられることによってこれらの操作の計算量もまた全要素数の対数オーダーとなるのだ。

おそらく、この文章では強調部分の「ノード内の」というところで筆が滑ってしまったのだと思う。
例えば、

Bツリーは全体としてソートされている（これは1文目と同じだ）。
Bツリーはファンアウトが大きいので二分探索ではないが、しかし似たようなやり方で部分木をたどることができる（3文目）。
その結果として、計算量は対数オーダーとなる（4文目）。

と2文目を無視して読めばその通りだ。もしくは「ノード内の」という部分だけ落としても良いと思う。
それとも普通は引っかからずに正しく読めるものなのだろうか？（純粋な疑問）

Kは何？ (2.3.3 Bツリーの検索の計算量)

曰く、

転送回数の観点から見ると、対数の底はN（ノードごとのキーの数）になります。それぞれの新規レベルにはK 倍のノードがあり、子ポインタをたどるごとに検索範囲は係数N ずつ減少します。検索時には、最大でもlog_K M（この場合のMはBツリー内の項目の総数）のページが、検索対象のキーを検出するために調べられます。また、ルートからリーフへのパスでたどる必要のある子ポインタの数は、レベルの数、言い換えればツリーの高さhとも等しくなります。

このKってNとは違うんですか？定義が分からない…

AとBの間にあるC (3.6 セルのレイアウト)

曰く、

キーセルには、セパレータキーと2 つの隣接するポインタの間にあるページへのポインタが保持されます。

保持されるのは

セパレータキー
2 つの隣接するポインタの間にあるページへのポインタ

の組であって、ページが「セパレータキー」と「～隣接するポインタ」の間にあるわけではない。

すべてのセル (3.6 セルのレイアウト)

曰く、

前提として、ページ内のすべてのセルは均一です。たとえば、すべてのセルがキーのみ、またはキーと値の両方の、いずれかを保持できます。

これは、全てのページにおいて

（ページ内の）すべてのセルがキーのみを保持している
（ページ内の）すべてのセルがキーと値の両方を保持している

のいずれかが成立することを意味しているが、「たとえば～」の文だけだとちょっと曖昧。自分だったらどう書くかなあ。

追加ポインタは何？ (3.8 可変長データの管理)

曰く、

局所性を改善するために、特にキーのサイズが小さいときには、一部の実装ではキーと値がリーフレベルで個別に格納されます。キーをまとめて格納したほうが、検索時の局所性を改善できます。検索対象のキーが検出された後で、その値は対応するインデックスを持つ値セルで検出できます。可変長キーでは、これによって、値セルの追加ポインタを計算して格納することが必要になります。

全体的に文章がこなれていないのはおいておいて、「追加ポインタ」とぽんと書かれても良く分からなかった。値セルへのポインタを追加で計算して格納することが必要になる、という意味？

ページが破損してたらどうするんだろう (3.10 チェックサム)

ページごとにチェックサムを計算する手法が紹介されているが、破損を検知したとして実際はどうしているのだろう。
エラーを出力してユーザにバックアップから復旧してもらうのかしら。

対応関係 (4.1.2 兄弟（Sibling）リンク)

曰く、

一部の実装では、前方および後方へのリンク、すなわち、左右の兄弟ページ（同じレベルでとなり合うページ、Siblingリンクとも言う）をポイントするものを格納します。

ここで対応しているのは

「前方および後方へのリンク」 = 「Siblingリンク」 = 「左右の兄弟ページをポイントするもの」
「左右の兄弟ページ」 = 「同じレベルでとなりあり合うページ」

である。ちなみに、兄弟リンクによって追加のロックが必要になるのにBlinkツリーのような並行性を持つ実装で有効になるという話が逆説的ですごい気になる。早くそこまで読み進めたい。

max_payload_sizeは何？ (4.1.5 オーバーフローページ)

曰く、

大半のBツリーの実装では、そのBツリーのノードに直接格納できるペイロードのバイト数は一定で、それを超えた残りはオーバーフローページに格納されます。この値は、ノードサイズをファンアウトで割って求められます。このアプローチを使用すると、ページに空き領域がなくなるという状況に陥ることがありません。少なくともmax_payload_size のバイトは常に確保されているからです。

max_payload_size = 「ノードサイズをファンアウトで割って求め」た値 = 「Bツリーのノードに直接格納できるペイロードのバイト数」で合ってますか？
また、この文章はノード内の各セルについて少なくともmax_payload_size分の領域が確保されている、と読めば良いですか？

C-ism (4.2 二分探索)

曰く、

二分探索アルゴリズムでは、ソートされた項目の配列と検索対象のキーを受け取り、数値を返します。返された数値が正である場合には、検索対象のキーが検出されたことを示し、入力配列内での検索対象の位置がその数値で指定されます。戻り値が負である場合には、検索対象のキーが入力配列内に存在しないことを示し、挿入位置がその数値で指定されます。

戻り値の正負に意味を込めるのがCっぽいなと思った（感想）。

ユースケースとして独立しているので (4.4 リバランシング)

曰く、

バランシングを行うと、コードが複雑になることがありますが、ユースケースとして独立しているので、最適化の一環として実装できます。

バランシングとユースケースの関係が分からない。バランシングがユースケース（Bツリーへの検索・挿入・削除といった操作のインターフェース）から独立しているということ？
例えば"Balancing can make the code complex, but it can be implemented as an optimization since it is independent of the use case."みたいな。

今後は読みながら更新していくつもり。

*1:自分は最初そう読んだ