B+treeで効率良く後方一致検索をする方法 - TechDoctor開発者Blog

初めまして、テックドクターのバックエンドエンジニアの魚木です。 私が担当するプロジェクトに、データベースのテーブルのあるカラムを前方一致検索する機能があります。そこに部分・後方一致検索もしたいという要望がありました。 そのデータベースはB+treeインデックスが使用されていますが、B+tree (または同系統のtree) インデックスは部分・後方一致検索は効率良くできないと言われています。 結果的に機能追加は見送られたのですが、前方・部分・後方一致検索の違いについて考えるよい機会になりました。 本記事は、B+treeが部分・後方一致検索を効率よくできない理由と、その代替手段として後方一致検索を高効率でする方法を説明します。 MySQLを前提としますが、インデックスの構造が同系統であれば同じような結論になります。 なぜ前方一致検索のみ高効率なのか まずはtree構造が前方一致検索を効率よく処

[ishikawadaiju]

編集しました！