All Projects → ggrandes → kvstore

ggrandes / kvstore

Licence: Apache-2.0 license
KVStore is a simple Key-Value Store based on B+Tree (disk & memory) for Java

Programming Languages

java
68154 projects - #9 most used programming language

Projects that are alternatives of or similar to kvstore

Bplustree
A minimal but extreme fast B+ tree indexing structure demo for billions of key-value storage
Stars: ✭ 1,598 (+1715.91%)
Mutual labels:  tree, btree
Kitdb
KitDB是一个内嵌式持久型的 高速NoSQL存储 lib
Stars: ✭ 439 (+398.86%)
Mutual labels:  disk, persistent
Vagrant Persistent Storage
A Vagrant plugin that creates a persistent storage and attaches it to guest machine.
Stars: ✭ 285 (+223.86%)
Mutual labels:  disk, persistent
Algorithms
Java implementation for Introduction to Algorithms book.
Stars: ✭ 58 (-34.09%)
Mutual labels:  tree, btree
Pibench
Benchmarking framework for index structures on persistent memory
Stars: ✭ 46 (-47.73%)
Mutual labels:  tree, index
treap
A thread-safe, persistent Treap (tree + heap) for ordered key-value mapping and priority sorting.
Stars: ✭ 23 (-73.86%)
Mutual labels:  tree, persistent
kdtree-rs
K-dimensional tree in Rust for fast geospatial indexing and lookup
Stars: ✭ 137 (+55.68%)
Mutual labels:  tree, index
Tinspin Indexes
Spatial index library with R*Tree, STR-Tree, Quadtree, CritBit, KD-Tree, CoverTree
Stars: ✭ 64 (-27.27%)
Mutual labels:  tree, index
RedisTree
Redis Tree (Ploytree) Structure Module
Stars: ✭ 64 (-27.27%)
Mutual labels:  tree, btree
un-flatten-tree
A small npm module for converting trees to lists and vice versa.
Stars: ✭ 14 (-84.09%)
Mutual labels:  tree
vue-virtualised
Blazing fast scrolling and updating for any amount of list and hierarchical data.
Stars: ✭ 18 (-79.55%)
Mutual labels:  tree
nub
A rendering and interaction Processing library
Stars: ✭ 28 (-68.18%)
Mutual labels:  tree
simpledbm
SimpleDBM is an Open Source Multi-Threaded Embeddable Transactional Database Engine in Java.
Stars: ✭ 51 (-42.05%)
Mutual labels:  btree
vscode-gcode-syntax
G Code Language Extension for Visual Studio Code. Turn VSCode into a fully capable G-Code editor, including language support & more.
Stars: ✭ 59 (-32.95%)
Mutual labels:  tree
avl array
High performance templated AVL tree using a fixed size array. Extensive test suite passing.
Stars: ✭ 33 (-62.5%)
Mutual labels:  tree
LoveTree
🌴爱情树,将相爱的时刻永远珍藏 (微信,QQ可完美查看)https://ajlovechina.github.io/LoveTree/
Stars: ✭ 295 (+235.23%)
Mutual labels:  tree
beehive
A flexible, modern, header-only implementation of behavior trees
Stars: ✭ 37 (-57.95%)
Mutual labels:  tree
mongodb-tree-structure
Implementing Tree Structure in MongoDB
Stars: ✭ 14 (-84.09%)
Mutual labels:  tree
SystemMonitor
Python script and a PyQt5 program to monitor ram and cpu usage along with disk usage.
Stars: ✭ 22 (-75%)
Mutual labels:  disk
android-thinkmap-treeview
Tree View; Mind map; Think map; tree map; custom view; 自定义;关系图;树状图;思维导图;组织机构图;层次图
Stars: ✭ 314 (+256.82%)
Mutual labels:  tree

KVStore

KVStore is a Key-Value Store based on B+Tree for Memory & Disk (for on disk, keys and values must be fixed length) for Java. Project is Open source (Apache License, Version 2.0)

API is similar to TreeMap.

Current Stable Version is 1.0.2


DOC

Usage Example

import java.util.Iterator;
import org.javastack.kvstore.KVStoreFactory;
import org.javastack.kvstore.Options;
import org.javastack.kvstore.holders.IntHolder;
import org.javastack.kvstore.structures.btree.BplusTree.TreeEntry;
import org.javastack.kvstore.structures.btree.BplusTreeFile;

public class Example {
	private static final String btreeFile = "/tmp/test";

	//
	public static void main(final String[] args) throws Exception {
		final int[] keys = new int[] { 5, 7, -11, 111, 0 };
		//
		KVStoreFactory<IntHolder, IntHolder> factory = new KVStoreFactory<IntHolder, IntHolder>(
				IntHolder.class, IntHolder.class);
		Options opts = factory.createTreeOptionsDefault()
				.set(KVStoreFactory.FILENAME, btreeFile);
		BplusTreeFile<IntHolder, IntHolder> tree = factory.createTreeFile(opts);
		//
		// Open & Recovery tree if needed
		try {
			if (tree.open())
				System.out.println("open tree ok");
		} catch (InvalidDataException e) {
			System.out.println("open tree error, recovery needed");
			if (tree.recovery(false) && tree.open()) {
				System.out.println("recovery ok, tree opened");
			} else {
				throw new Exception("Fatal Error Opening Tree");
			}
		}
		// clear all previous content if any
		tree.clear();
		// ============== PUT
		for (int i = 0; i < keys.length; i++) {
			final IntHolder key = IntHolder.valueOf(keys[i]);
			final IntHolder value = IntHolder.valueOf(i);
			tree.put(key, value);
		}
		tree.sync();
		// ============== GET
		System.out.println("tree.get(7)=" + tree.get(IntHolder.valueOf(7)));
		// ============== REMOVE
		tree.remove(IntHolder.valueOf(7));
		// ============== ITERATOR
		for (Iterator<TreeEntry<IntHolder, IntHolder>> i = tree.iterator(); i
				.hasNext();) {
			TreeEntry<IntHolder, IntHolder> e = i.next();
			System.out.println("Key=" + e.getKey() + " Value=" + e.getValue());
		}
		// ============== FIRST / LAST
		System.out.println("tree.firstKey()=" + tree.firstKey());
		System.out.println("tree.lastKey()=" + tree.lastKey());
		//
		tree.sync();
		tree.close();
	}
}
The Result:
tree.get(7)=1
Key=-11 Value=2
Key=0 Value=4
Key=5 Value=0
Key=111 Value=3
tree.firstKey()=-11
tree.lastKey()=111

MAVEN

Add the KVStore dependency to your pom.xml:

<dependency>
    <groupId>org.javastack</groupId>
    <artifactId>kvstore</artifactId>
    <version>1.0.2</version>
</dependency>

TODOs

  • A lot of Doc
  • Describe disk formats
  • HashMap on disk
  • Separate size of read cache and write cache

DONEs

  • BlockStore (Fixed length chunks)
    • Support for mmaped files
  • StreamStore (Variable length chunks)
  • B+Tree for Index
    • Buffer reuse
    • Memory mode
    • Persistence on disk (BlockStore)
      • Cache of nodes
      • Reuse free blocks on disk
      • Redo log
      • Recovery system
      • Allow open without populate read cache
      • Allow open readOnly mode
      • File locking (multi-process)
  • HashMaps for natives (memory)
  • Holders for data and NIO serialization
    • Fixed length
      • Boolean
      • Byte
      • Short
      • Integer
      • Long
      • Null
    • Variable length
      • Strings
  • Create Factory
  • Options object for factory
  • Use Log4J
  • Maven repository

MISC


Benchmarks

Values are not accurate, but orientative. Higher better. All test Running on Laptop { Windows Vista (32bits), Core 2 Duo 1.4Ghz (U9400), 4GB Ram, Magnetic Disk (WDC-WD5000BEVT-22ZAT0) }.
Test-1 Writes/s Reads/s
BlockStore (RAF) 46k 58k
BlockStore (MMAP) 67k 182k
StreamStore 101k 55k
Test-1 (org.javastack.kvstore.test.BenchMarkDiskStore): Registry { count=1e6, datalen=256bytes } BlockStore { blockSize=512 (2reg/block), fileSize=250MB } StreamStore { outBufferSize=0x10000, align=true, fileSize=256MB }
Test-2 Put/s Get/s Remove/s
BplusTreeMemory 457k 1041k 324k
IntHashMap 1154k 31250k 16000k
IntLinkedHashMap 1114k 31250k 11696k
Test-2 (org.javastack.kvstore.test.BenchMarkMemoryStructures): Registry { count=2e6, datalen=256bytes } BplusTreeMemory { key=Integer, b-order=511 } IntHashMap { initialSize=(2e6 * 2) }

Inspired in Book: Open Data Structures in Java, Perl DB_File, JDBM3 and H2-Database, this code is Java-minimalistic version.

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].