YOI 759：同じ回数だけ比べても、遅い記憶を読む回数は木の分岐で決まる

論文759 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/759 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.23015187）。

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi759,
  author = {Yamagishi, Yuuki},
  title = {Comparing Equally Often, the Number of Slow-Memory Reads Is Set by the Tree's Branching},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/759},
  doi = {10.5281/zenodo.23015187},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

二分探索も木の索引も、探す手間は要素の数の対数で増える。だから同じだと言われやすい。比べる回数と、遅い記憶を読む回数を分けて数える。新しい定理も法則も主張しない。

第一に、比べる回数は、木の分岐に依らず同じである。要素 $10^{9}$ 個で、二分探索も分岐 $100$ の木も $\mathbf{29.897353}$ 回（第2節）。

第二に、遅い記憶を読む回数は、大きく違う。一ページ $100$ 個で、二分探索 $\mathbf{24.253497}$、木 $\mathbf{4.500000}$（第2節）。

第三に、これが本稿の芯である。読む回数の比は、対数の底の比に近づく。比は $10^{9}$ 個で $\mathbf{5.389666}$、$10^{18}$ 個で $\mathbf{6.016761}$ と増え、$\log_{2}100=\mathbf{6.643856}$ を超えない（第3節）。

第四に、小さい表では差が小さい。$10^{3}$ 個で比は $\mathbf{2.881285}$（第3節）。

第五に、試行でも同じ向きに出る。要素 $10^{6}$ 個・$2000$ 回で、読むページは二分探索 $\mathbf{13.212000}$、木 $\mathbf{3.000000}$（第3節）。

第六に、分離子は、数えているのが比較の回数か、ページの読み出しの回数かである。「どちらも対数」は、何を数えるかを言うまで速さを語れない（第4節）。

キーワード：二分探索、B木、索引、対数の底、ページの読み出し、記憶の階層

Abstract

Both binary search and a tree index take effort growing as the logarithm of the number of elements, and so are readily called the same.Comparisons and reads of slow memory are counted separately.No new theorem or law is claimed.

First, the number of comparisons does not depend on the tree’s branching、with $10^{9}$ elements, $\mathbf{29.897353}$ for binary search and for a tree of branching $100$ alike (Section 2).

Second, reads of slow memory differ greatly、with $100$ elements per page, $\mathbf{24.253497}$ for binary search and $\mathbf{4.500000}$ for the tree (Section 2).

Third, and this is the core. The ratio of reads approaches the ratio of logarithm bases、$\mathbf{5.389666}$ at $10^{9}$ elements and $\mathbf{6.016761}$ at $10^{18}$, never exceeding $\log_{2}100=\mathbf{6.643856}$ (Section 3).

Fourth, small tables differ less、the ratio is $\mathbf{2.881285}$ at $10^{3}$ elements (Section 3).

Fifth, a trial shows the same direction、with $10^{6}$ elements and $2000$ searches, pages read average $\mathbf{13.212000}$ for binary search and $\mathbf{3.000000}$ for the tree (Section 3).

Sixth, the separator is whether one counts comparisons or page reads、“both are logarithmic” says nothing about speed until one says what is counted (Section 4).

Keywords: binary search, B-tree, index, base of the logarithm, page reads, memory hierarchy

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/759/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/759 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ