d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ B+木とは B+木は、m分木をもとにしたデータ構造です。 m分木とは節が最大 個 の子をもつことができる木構造で、二分木の一般化といえます。 B+木では、データをもつのは葉のみで、葉以外の節はキーだけをもつ構成をとっています。 以下の条件を満たすものをm階のB+木と呼びます。 根は葉であるか、あるいは 個 の子をもてる 根、葉以外の節は、 個の子をもっている。 根からすべての葉までの経路の長さが等しい。 条件3によって、B+木は常に長さが等しくバランスがとれていることになります。 個の要素をもつB+木の高さは、最悪のケースで 程度、最良のケースで 程度になります。 通常 は に比べて十分小さい… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F01%2F21%2F173057" title="B+木の概要と実装 - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%20m%E5%80%8B%20%28m%E2%89%A72%29 Hatena Blog https://hatena.blog 2018-01-21 17:30:57 rich https://tutuz.hateblo.jp/entry/2018/01/21/173057 1.0 100%