btree4j

A efficient B+-tree implementation written in pure Java

License	License Apache License, Version 2.0
GroupId	GroupId io.github.myui
ArtifactId	ArtifactId btree4j
Last Version	Last Version 0.9.1
Release Date	Release Date Aug 5, 2020
Type	Type jar
Description	Description btree4j A efficient B+-tree implementation written in pure Java
Project URL	Project URL https://github.com/myui/btree4j
Project Organization	Project Organization Makoto Yui
Source Code Management	Source Code Management https://github.com/myui/btree4j

Download btree4j

Filename	Size
btree4j-0.9.1.pom
btree4j-0.9.1.jar	164 KB
btree4j-0.9.1-sources.jar	88 KB
btree4j-0.9.1-javadoc.jar	946 KB
Browse

How to add to project

Apache Maven

<!-- https://jarcasting.com/artifacts/io.github.myui/btree4j/ -->
<dependency>
    <groupId>io.github.myui</groupId>
    <artifactId>btree4j</artifactId>
    <version>0.9.1</version>
</dependency>

Gradle Groovy

// https://jarcasting.com/artifacts/io.github.myui/btree4j/
implementation 'io.github.myui:btree4j:0.9.1'

Gradle Kotlin

// https://jarcasting.com/artifacts/io.github.myui/btree4j/
implementation ("io.github.myui:btree4j:0.9.1")

Apache Buildr

'io.github.myui:btree4j:jar:0.9.1'

Apache Ivy

<dependency org="io.github.myui" name="btree4j" rev="0.9.1">
  <artifact name="btree4j" type="jar" />
</dependency>

Groovy Grape

@Grapes(
@Grab(group='io.github.myui', module='btree4j', version='0.9.1')
)

Scala SBT

libraryDependencies += "io.github.myui" % "btree4j" % "0.9.1"

Leiningen

[io.github.myui/btree4j "0.9.1"]

Dependencies

compile (3)

Group / Artifact	Type	Version
log4j : log4j	jar	1.2.17
commons-cli : commons-cli	jar	1.2
commons-logging : commons-logging	jar	1.0.4

provided (1)

Group / Artifact	Type	Version
com.google.code.findbugs : jsr305	jar	3.0.2

test (3)

Group / Artifact	Type	Version
junit : junit	jar	4.12
org.openjdk.jmh : jmh-core	jar	1.20
org.openjdk.jmh : jmh-generator-annprocess	jar	1.20

Project Modules

There are no modules declared in this project.

btree4j: Disk-based Prefix B+-tree written in Pure Java

What's Btree4j

Btree4j is a disk-based Prefix B+-tree written in Pure Java.

It's pretty fast and 100k ops/sec is expected even on laptop.

Using btree4j

<dependency>
    <groupId>io.github.myui</groupId>
    <artifactId>btree4j</artifactId>
    <version>0.9.1</version>
</dependency>

Find usage in unit tests.

Features and Strength

Applied many improvements over the original Xindice's implementation as follows:

Implementes Prefix B+-tree in which prefixes are selected carefully to minimize their length. In prefix B+-tree, key prefixes are managed by a TRIE-like smart algorithm.

Rudolf Bayer and Karl Unterauer. "Prefix B-trees", Proc. ACM Trans. Database Syst. 2, 1, pp.11-26), March 1977. [DOI]

Pointers are compressed using Variable Byte Codes so that more keys/values are fit in memory.
Support both unique and non-unique indexing. Storing duplicate keys is allowed for non-unique indexing.
Index file based on B+-tree is supported. Multiple values per a key is also supported. BTreeIndex stores <bytes[] KEY, byte[] VALUE> with VALUE stored on distinct data pages and pointers to them are managed by B+-Tree to avoid consuming many disk pages for large values in B+-tree.
Support variable-length key/value
Prefix and range search is supported in addition to exact match using a flexible callback handler. Support LIKE match using wildcards.
Paging (virtual memory) support using LRU cache replacement policy and Freespace management.
Deletion and updates are, of course, supported.
Support efficient Bulk-loading.
Minimum dependencies to external libraries. Runs on Java 8 or later.

Credits

This software is originally developed for XBird based on Apache Xindice.

Versions

Version
0.9.1 Aug 5, 2020
0.9.0 Jun 30, 2020

btree4j

License

GroupId

ArtifactId

Last Version

Release Date

Type

Description

Project URL

Project Organization

Source Code Management