Reading: AlphaSort

AlphaSort

概要

CPU cache-sensitive なソート方法について論じた論文。 内部的には (key-prefix, the pointer to a record) のタプルをキーにした QuickSort を使う。

何が新しいか

cache locality を考慮に入れてソート方法を選択している点。 quick sort は cache に優しい。

アルゴリズム

  1. ディスクから読み込んだレコード群を入力として quick sort を実行する。
  2. ソート順序は (key-prefix, pointer) のペアで決める。
  3. quick sort で生成したデータは replace-selection tree を使ってマージする。

Comments

comments powered by Disqus