続 単純な場合の Skip Graphs アルゴリズムを実装してみた 3
動作の主体が明確になるように search-op, insert-op, buddy-op, link-op を書き直した。
buddy-op の実装が論文に載っていないので若干苦労したが多分実装できたと思う。論文中の buddy-op の引数と戻り値は微妙な気がした。
まだまだ実装の重複や未実装があるが、日記に進捗を書いておかないと破綻しそうなのでメモ。
やった事
- lock 必要箇所検討
- concurrent join に関して論文を読んだ
- Level 3 以上に対応
- 動作の主体を明確に
- ノードの削除
- membership vector をまじめに実装
- limit つきの range search
まだ
- 修復アルゴリズム
- Multi key skip graphs
- 各種コードの重複削除
- range-search も search-op で。
- delete-op。
- level の動的引き上げ
