「データ構造」の記事一覧

• コンパクト・エラスティック・バイナリーツリーの設計と応用

  2025-05-05 09:25

  科学・技術

  cebtreeは、最小限のメモリ使用で高速なデータ構造を実現するために設計された、新しい形式のバイナリーツリーです。ノードに親ポインタを持たず、わずか2つのポインタで構成され、空間効率に優れています。重複キー対応、タグ付きポインタ、相対ポインタなどの実装を経て、haproxyの変数や設定における検索効率を向上させる実用性が確認されました。今後は並列処理対応やさらなる汎用性の拡大が期待されています。

• 高速なデータ照合を可能にするBloomフィルターの仕組み

  2025-05-02 03:46

  科学・技術

  Bloomフィルターは、ある要素が集合に含まれているかを高速かつ省メモリで確認できる確率的データ構造です。ビット配列と複数のハッシュ関数を使い、否定の確認には確実性があり、肯定の場合にはごく稀に誤判定が含まれます。Go言語での実装例も紹介され、1秒間に数千万件の検査も可能です。特にアクセスの大半が否定となる用途で真価を発揮します。