O記法で出てくるlog（対数）について調べた

Webエンジニアのための データベース技術[実践]入門 (Software Design plus)

P.24

多分木と二分木
ブランチやリーフの枝分かれ本数が2本しかないものを特に「二分木」と呼びます。B+Treeは「多分木」と呼ばれており、枝分かれ本数は2本どころではなく数十本から数百本にわたることもあります。枝分かれ本数を多くする理由は、階層の段数を減らしてアクセス回数を少なくするためです。
二分木の場合、N階層あたり2N個しかレコードを管理できません。図2-3の例であれば3層で済んでいたところが二分木になると16層ものの深さになってしまい、そのぶん多数回のアクセスが必要になってしまいます。二分木の場合、レコード数Nあたりの探索に必要な計算量がO(log2 N)になることが知られています。O(N)とは比べ物にならないほど効率が良いですが、ハッシュインデックスのO(1)と比べれば効率が落ちます。B+Treeのような多分木の構成を取ることで、O(logm N)に持ち込むことができ、図2-3のようにアクセス数を大幅に減らすことができます。

書きかけです。後で追記する。

参考

• 対数とはどんな数か？