Show HN: ChaosTree – 依存関係ゼロのJavaツリーライブラリ (AVL, RBT, B-Tree, B+Tree)

ChaosTreeとは？

ChaosTreeは、複数のツリー実装を中心に構築された、依存関係ゼロのJava Sorted Set/Mapライブラリです。

以下の実装を提供します:

• AVL Tree
• Red-Black Tree
• B-Tree
• B+Tree

NavigableSet, NavigableMap, SequencedSet, SequencedMapを実装しているため、カスタムAPIは作成していません。私のカスタムAPIは以下の通りです:

• buildFromSorted(Iterator> it, float factor)
• importFlatMatrix(Object[][] blast, float factor)
• exportFlatMatrix()

ChaosTreeを開始したのは、データ構造の学習をどこまで進められるか探求したかったからです。最初はカスタムAPIを持つ7種類のSet型ツリーの最初のリリースとして始まりました。没頭するにつれてMapへと移行しました。SetからMapへの移行フェーズでは劇的な変化と知識のアップグレードがあり、JDK11+サポートからJDK21+へとツリーの限界を押し広げ、依存関係ゼロ、メモリレイアウト、アロケーション、JVMの挙動、実世界のパフォーマンスに細心の注意を払いました。

実験したことの一部:

• さまざまなノードレイアウトとメタデータフットプリント
• ツリー実装のためのCRTP/F-boundedポリモーフィズム
• 親ポインタ付きノード vs 親ポインタなしノード
• 配列ベースのN進木ノード
• B-Tree/B+Treeの次数選択
• JMHベンチマークとJFRプロファイリング
• java.util.TreeMap/TreeSetに対する差分/ランダムテスト

この困難な作業を経て、以下のテストもパスしました:

• Guava Testlib互換性テスト
• jqwikプロパティベーステスト
• リファレンスコレクションに対するランダム差分テスト
• ツリーノードのホワイトボックス構造検証
• B-Tree/B+Treeの構造的不変性の直接検証
• 例外およびイテレータ契約テスト
• シリアライゼーションおよびクローニングテスト
• N進木はAPI検証のためのカスタムjqwikテストも使用しています。

テールレイテンシの挙動は、単純なテキストに切り詰められてしまい、データが誤って読まれるため、ここでは表示されていません: https://chaos-vy.github.io/ChaosTree/utils/JMH-Report.html 公式JDKのTreeMapに対するベンチマークも実行しました。N進木へのアップデートも行いました。

GitHub: https://github.com/Chaos-vy/ChaosTree https://chaos-vy.github.io/ChaosTree/

特にAPI設計、実装選択、ベンチマーク手法についてフィードバックをいただけると幸いです。現在、パフォーマンスチューニングのために不要で複雑なブランチを切り詰めることを試みています。