Présentation

ChaosTree est une bibliothèque Java sans dépendance externe qui implémente quatre structures de recherche ordonnée : AVL, Red‑Black, B‑Tree et B+Tree. Elle expose des implémentations Set et Map conformes aux contrats NavigableSet, NavigableMap, SequencedSet et SequencedMap introduits avec JDK 21. La version 2.0.0, disponible via Maven (

<dependency>
    <groupId>io.github.chaos-vy</groupId>
    <artifactId>chaos-tree</artifactId>
    <version>2.0.0</version>
</dependency>
), cible les applications nécessitant des lectures massives et des balayages de plages.

Architecture et optimisation cache

Le moteur « N‑ary » regroupe B‑Tree et B+Tree dans une représentation à base de tableaux pré‑alloués dont la capacité exacte est définie par un facteur d’occupation configurable entre 0,5 et 1,0. Cette densité réduit le nombre de références indirectes et augmente les taux de hit L1/L2 d’environ 40 % lors de scans de grande taille, comme indiqué dans le rapport JMH fourni. Le B+Tree pousse les valeurs réelles dans une liste doublement chaînée au niveau des feuilles, ce qui minimise les déplacements de mémoire et élimine le churn du ramasse‑miettes pendant les lectures. Le moteur « binary » (AVL, RBT) conserve une structure point‑query classique, adaptée aux accès aléatoires où la densité maximale du N‑ary n’est pas indispensable.

Validation et performances mesurées

ChaosTree est soumis à plus de 214 000 tests générés par Guava Testlib, garantissant une conformité fonctionnelle exacte avec java.util.TreeMap et TreeSet. Des tests de propriétés basés sur jqwik exécutent des centaines de milliers de scénarios aléatoires, vérifiant les invariants de hauteur, d’équilibrage et d’occupation des nœuds. Le benchmark JMH, disponible dans docs/Benchmark_Analysis.html, montre des temps de parcours de sous‑cartes (ex. subMap(1, true, 3, true)) inférieurs de 30 % aux implémentations standards, tout en maintenant une pause GC maximale de 82 ms. La sérialisation et le clonage sont supportés avec une complexité O(N) lors du chargement en masse.

Limites d’utilisation

Les API de chargement en masse (buildFromSorted, importFlatMatrix) ne fonctionnent que sur un arbre vide et exigent des données pré‑triées, ce qui exclut les opérations addFirst() et addLast() – elles lèvent immédiatement UnsupportedOperationException. La bibliothèque requiert JDK 21 ou supérieur, et son modèle de licence ne prévoit pas de support pour les environnements antérieurs. Enfin, le facteur d’occupation ne peut être inférieur à 0,5, limitant la flexibilité d’allocation dans les scénarios où la densité très faible serait souhaitable.