GitHub - Chaos-vy/ChaosTree: Zero-dependency Java tree library featuring binary and N-ary families with JMH benchmarks and hardware-counter-backed performance evidence. · GitHub

Skip to content

Navigation MenuSign inAppearance settingsPlatformAI CODE CREATIONGitHub CopilotWrite better code with AIGitHub Copilot appDirect agents from issue to mergeMCP RegistryIntegrate external toolsDEVELOPER WORKFLOWSActionsAutomate any workflowCodespacesInstant dev environmentsIssuesPlan and track workCode ReviewManage code changesCode QualityEnforce quality at mergeAPPLICATION SECURITYGitHub Advanced SecurityFind and fix vulnerabilitiesCode securitySecure your code as you buildSecret protectionStop leaks before they startEXPLOREWhy GitHubDocumentationBlogChangelogMarketplaceView all featuresSolutionsBY COMPANY SIZEEnterprisesSmall and medium teamsStartupsNonprofitsBY USE CASEApp ModernizationDevSecOpsDevOpsCI/CDView all use casesBY INDUSTRYHealthcareFinancial servicesManufacturingGovernmentView all industriesView all solutionsResourcesEXPLORE BY TOPICAISoftware DevelopmentDevOpsSecurityView all topicsEXPLORE BY TYPECustomer storiesEvents & webinarsEbooks & reportsBusiness insightsGitHub SkillsSUPPORT & SERVICESDocumentationCustomer supportCommunity forumTrust centerPartnersView all resourcesOpen SourceCOMMUNITYGitHub SponsorsFund open source developersPROGRAMSSecurity LabMaintainer CommunityGitHub StarsArchive ProgramREPOSITORIESTopicsTrendingCollectionsEnterpriseENTERPRISE SOLUTIONSEnterprise platformAI-powered developer platformAVAILABLE ADD-ONSGitHub Advanced SecurityEnterprise-grade security featuresCopilot for BusinessEnterprise-grade AI featuresPremium SupportEnterprise-grade 24/7 supportPricingSearch/Sign inSign upAppearance settings

You signed in with another tab or window. Reload to refresh your session.
You signed out in another tab or window. Reload to refresh your session.
You switched accounts on another tab or window. Reload to refresh your session.

Dismiss alert

Chaos-vy

/

ChaosTree

Public

Notifications
You must be signed in to change notification settings

Fork
2

Star
20

Code

Issues
0

Pull requests
0

Discussions

Actions

Projects

Security and quality
0

Insights

Additional navigation options

Code

Issues

Pull requests

Discussions

Actions

Projects

Security and quality

Insights

mainBranchesTagsGo to fileCodeOpen more actions menuLatest commit History408 Commits408 CommitsFolders and filesNameNameLast commit messageLast commit date.github/workflows.github/workflows  chaos-treechaos-tree  ct-benchmarkct-benchmark  ct-examplesct-examples  ct-jcstressct-jcstress  docsdocs  .gitignore.gitignore  CHANGELOG.mdCHANGELOG.md  CODE_OF_CONDUCT.mdCODE_OF_CONDUCT.md  CONTRIBUTING.mdCONTRIBUTING.md  LICENSELICENSE  README.mdREADME.md  pom.xmlpom.xml  View all filesRepository files navigationREADMECode of conductContributingApache-2.0 licenseMore items

What is ChaosTree?
ChaosTree is a Java Sorted Set/Map library built around multiple search-tree data structures, including AVL Trees, Red-Black Trees, B-Trees, and B+ Trees.
The library provides both Set and Map implementations, with APIs designed around the semantics of the JDK's NavigableSet, NavigableMap, SequencedSet, and SequencedMap contracts.
In addition to the standard collection APIs, ChaosTree provides specialized construction APIs for users who want direct control over the initial structure of N-ary trees, Do read

buildFromSorted(Iterator, factor)
importFlatMatrix(Object[][], factor)

These APIs allow users to control the target node occupancy through a configurable factor in the supported range [0.5, 1.0], while maintaining the structural invariants required by the underlying B-Tree/B+Tree design.
Correctness & Validation
ChaosTree is validated through multiple layers of testing:

Guava Testlib compatibility testing
jqwik property-based testing
Randomized differential testing against reference collections
White-box structural validation of tree nodes
Direct validation of B-Tree/B+Tree structural invariants
Exception and iterator-contract testing
Serialization and cloning tests

The structural tests inspect the internal tree representation rather than relying solely on externally observable behavior. This provides an additional layer of validation for node occupancy, ordering, topology, and balancing invariants.
Performance claims are backed by reproducible JMH benchmark configurations. If a referenced benchmark source is missing from the repository due to project cleanup, it can be restored or replaced with an updated benchmark.
Why ChaosTree?

Cache-Locality First: The N-ary engine packs data tightly into pre-allocated exact-capacity arrays, drastically improving L1/L2 CPU cache hit rates and memory load stalls by nearly 40% during large range scans.
Strictly Compatible: Leverages the new JDK 21 SequencedCollection, SequencedSet, and SequencedMap interfaces. It passes the Guava Testlib (214,000+ tests) to enforce identical semantics to java.util.TreeMap and TreeSet.
Public Bulk Load: I do explicitly provide two powerful API through which user is allowed to build the N-ary tree family, It only works at empty tree. Need sorted data. Verified tested.
Serializable & Cloneable Each tree supports Serialization (Bulk load O(N)) as well as Cloneable.

Requirements

Minimum JDK: 0xCAFEBABE 0000 0041 | JDK 21+
Build Tool: Maven 3.8+

Details about ChaosTree: https://chaos-vy.github.io/ChaosTree/index.html
(Note: As strictly sorted structures, addFirst() and addLast() are unsupported and fail-fast).
Getting ChaosTree
Maven coordinates
<dependency>
<groupId>io.github.chaos-vy</groupId>
<artifactId>chaos-tree</artifactId>
<version>2.0.0</version>
</dependency>
Gradle
implementation("io.github.chaos-vy:chaos-tree:2.0.0")
Quick start
Create a highly-optimized BPlusTreeMap to leverage the N-ary engine:
import chaos.tree.naryMap.BPlusTreeMap;
import java.util.NavigableMap;

public class Main {
public static void main(String[] args) {
// Degree 64 B+Tree Map
NavigableMap<Integer, String> map = new BPlusTreeMap<>();

map.put(1, "Chaos");
map.put(2, "Tree");
map.put(3, "Performance");

// Instant range scans traversing the contiguous leaf-linked list
NavigableMap<Integer, String> subMap = map.subMap(1, true, 3, true);
System.out.println(subMap);
}
}
Data Structures and Architecture
ChaosTree is split into two foundational engines:

The N-ary Family (Sets & Maps): BTree, BPlusTree. Built for maximum read throughput, large-scale range scans, and zero GC churn. The BPlusTree pushes all real data to a contiguous double linked-list at the bottom layer, allowing high read through put.
The Binary Family (Sets): AVL, RBT, . Built for fast point-queries and everyday data storage where the extreme caching of the N-ary engine is not required.

Testing & Thread-Safety
I wanted ChaosTree to be correct just as much as I wanted it to be fast. It is validated by these following testing suite:

Guava Testlib: ChaosTree passes 214,000+ generated test cases validating exact java.util.NavigableMap and NavigableSet for all tree.
The Fuzz Test: Trees are subjected to hundreds of thousands of completely randomized property tests via jqwik to verify structural invariants against a source-of-truth (java.util.TreeMap). Due to Nary API node structure of 32 the new node never got created in Guava So I explicitly designed the verify API which verify explicitly for that.
Strict Contracts: Enforces fail-fast ConcurrentModificationException iterator semantics, exact size counting, and strict Null-Pointer guards on custom Comparators.

Documentation

Architecture Decision Records: docs/ADR.html
JMH GC Profiling & The 82ms Pause: docs/utils/JMH-Report.html
Throughput & CPU Benchmarks: docs/Benchmark_Analysis.html
The Testing Journey: docs/Test_Journey.html
Release history: CHANGELOG.md
Contributing guide: CONTRIBUTING.md

Support and contributions

Bugs and features: GitHub Issues
Discussion: GitHub Discussions

Pull requests and well-scoped issue reports for compatibility, correctness, and maintenance work are welcome!

AboutZero-dependency Java tree library featuring binary and N-ary families with JMH benchmarks and hardware-counter-backed performance evidence.chaos-vy.github.io/ChaosTree/Topicsavl-treebplus-treebtreecollectionsdata-structuresjavajmh-benchmarkmavenperformancered-black-treesearchtreeResourcesReadmeApache-2.0 licenseCode of conductCode of conductContributingContributingActivityStars20 starsWatchers1 watchingForks2 forksReport repositoryReleasesPackagesUsed byContributorsLanguages

Footer

© 2026 GitHub, Inc.

Footer navigation

Terms

Privacy

Security

Status

Community

Docs

Contact

Manage cookies

Do not share my personal information

You can’t perform that action at this time.

ChaosTree is a zero-dependency Java library designed to implement sorted set and map data structures by utilizing multiple underlying search-tree data structures, including the AVL Tree, Red-Black Tree, B-Trees, and B+ Trees. The library provides APIs that adhere to the contracts defined by the Java standard library interfaces such as NavigableSet, NavigableMap, SequencedSet, and SequencedMap. Beyond standard collection operations, ChaosTree incorporates specialized construction APIs, such as buildFromSorted and importFlatMatrix, which allow users to directly control the initial structure of the N-ary tree family using a configurable factor, while maintaining the necessary structural invariants of the underlying B-Tree or B+Tree design.

The library is architecturally split into two foundational engines: the N-ary family, which encompasses BTree and BPlusTree, and the Binary family, which includes AVL and RBT. The N-ary engine is specifically optimized for high read throughput, large-scale range scans, and minimizing garbage collection overhead. This is achieved by packing data tightly into pre-allocated exact-capacity arrays, which significantly improves L1/L2 CPU cache hit rates and reduces memory load stalls by nearly forty percent during extensive range operations. In contrast, the Binary family is optimized for fast point-queries and general data storage where the extreme caching benefits of the N-ary engine are less critical.

The correctness and reliability of ChaosTree are strongly established through a comprehensive validation process. This includes compatibility testing against the Guava Testlib, which executes over two hundred thousand test cases to ensure identical semantic behavior with java.util.TreeMap and TreeSet. Furthermore, the library undergoes rigorous property-based testing using jqwik against reference collections, randomized differential testing, and white-box structural validation of the tree nodes to inspect invariants related to ordering, topology, and balancing. The system strictly enforces iterator semantics, exact size counting, and robust null-pointer guards. Performance claims are substantiated by reproducible benchmarks using JMH, along with evidence derived from hardware counters.

The implementation also ensures data persistence and integrity through support for serialization and cloning across all tree structures. Although the library provides powerful bulk loading capabilities for the N-ary trees, it enforces a fail-fast principle, explicitly disallowing methods like addFirst() and addLast() to maintain structural integrity. The minimum requirements for using ChaosTree necessitate a Java Development Kit version of 21 or later and a Maven build tool version of 3.8 or newer.