Home
Softono
B-tree

B-tree

Open source
GitHub
20
Stars
2
Forks
0
Issues
2
Watchers
9 years
Last Commit
NoSQL Databases Developer Tools

About B-tree

FriendlyCSharp.Databases is a cross-platform C library implementing generic B-tree data structures for in-memory storage. It offers four B-tree variants: FcsBTreeN, FcsFastBTreeN, FcsLockBTreeN, and FcsFastLockBTreeN, each supporting generic key-value pairs with sorted keys and duplicate keys. The library provides methods for adding, finding, searching, updating, deleting, and navigating records, with fast variants offering optimized traversal operations and lock variants supporting thread-safe concurrent access. The B-tree implementation can serve as a replacement for NoSQL in-memory databases in real-time scenarios such as Firebase, Redis Cache, SAP HANA, and other OLTP systems. The structure ensures logarithmic time complexity for searches, insertions, deletions, and sequential access. Designed for .NET Standard 1.1, the library is suitable for building high-performance cache layers, embedding database functionality into applications, and prototyping data storage solutions. Source code is available on GitH

Platforms

Web Self-hosted

Links

Source Code
f
Published by
friendlycsharp
Visit View Profile

README.md

View on GitHub

FriendlyCSharp.Databases

A library of cross platform C# data structures. Generic B-tree written in C#, which can be replaced with NoSQL database stored in the memory of discharge requirements in real-time (Firebase, Redis Cache, SAP HANA, Exadata, OLTP, etc.). Basic information B-tree can be found in the book N. Wirth, Algorithms + data structures = programs and on Wikipedia, namely:

"In computer science, a B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children (Comer 1979, p. 123). Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. B-trees are a good example of a data structure for external memory. It is commonly used in databases and filesystems. (...) Rudolf Bayer and Ed McCreight invented the B-tree while working at Boeing Research Labs in 1971 (Bayer & McCreight 1972), but they did not explain what, if anything, the B stands for." - Wikipedia.

 

B-Tree generic class

FcsBTreeN<TKey, TValue>

  • Methods: BtnCompares, BtnUpdates, BtnAdd, BtnDeleteAll, BtnFind, BtnFirst, BtnLast, BtnNext, BtnPrev, BtnSearch, BtnSearchPrev, BtnUpdate and BtnUsedKeys.

    FcsFastBTreeN<TKey, TValue>

  • Methods: BtnCompares, BtnUpdates, BtnAdd, BtnDeleteAll, BtnFind, BtnFirst, BtnLast, BtnNext, BtnPrev, BtnSearch, BtnSearchPrev, BtnUpdate and BtnUsedKeys.
  • Methods: BtnFastFind, BtnFastFirst, BtnFastLast, BtnFastNext, BtnFastPrev, BtnFastSearch, BtnFastSearchPrev.

    FcsLockBTreeN<TKey, TValue>

  • Methods: BtnCompares, BtnUpdates, BtnAdd, BtnDeleteAll, BtnFind, BtnFirst, BtnLast, BtnNext, BtnPrev, BtnSearch, BtnSearchPrev, BtnUpdate and BtnUsedKeys.

    FcsFastLockBTreeN<TKey, TValue>

  • Methods: BtnCompares, BtnUpdates, BtnAdd, BtnDeleteAll, BtnFind, BtnFirst, BtnLast, BtnNext, BtnPrev, BtnSearch, BtnSearchPrev, BtnUpdate and BtnUsedKeys.
  • Methods: BtnFastFind, BtnFastFirst, BtnFastLast, BtnFastNext, BtnFastPrev, BtnFastSearch, BtnFastSearchPrev.

Source code

See the Github.

Performance

A B-tree of order m is a tree which satisfies the following properties:

  1. Every node has at most m children.
  2. Every non-leaf node (except root) has at least ⌈m/2⌉ children.
  3. The root has at least two children if it is not a leaf node.
  4. A non-leaf node with k children contains k−1 keys.
  5. All leaves appear in the same level.
generic class sorted by key duplicate keys B-tree locking records
fastDB<...> Yes Yes Yes Yes
FcsBTreeN<TKey, TValue> Yes Yes Yes No
FcsFastBTreeN<TKey, TValue> Yes Yes Yes No
FcsLockBTreeN<TKey, TValue> Yes Yes Yes No
FcsFastLockBTreeN<TKey, TValue> Yes Yes Yes No
SortedSet<KeyValuePair<TKey, TValue>> Yes No No No
HashSet<KeyValuePair<TKey, TValue>> No No No No
Dictionary<TKey, TValue> No No No No

Benchmark

The benchmark was configured as follows:

  • CPU: Intel Xeon E3-1245 @ 3.3 GHz;
  • Windows 10, 64bit, .NET Standard 1.1
  • 4x4GB DDR3 Kingston @ 1333 MHz

Adding in a single thread:

<int, uint> sorted by key iteration total (ms) one time (ns) speed RAM (MB) occupied
FcsFastBTreeN<...> Yes 10,000,000 6,185 619 100% 128 100%
SortedSet<...> Yes 10,000,000  19,443   1,944   32%   458   358% 
HashSet<...> No 10,000,000 2,017 202 307% 229 179%
Dictionary<...> No 10,000,000 1,378 138 449% 229 179%

Foreach in a single thread:

<int, uint> sorted by key iteration total (ms) one time (ns) speed IOPS
fastDB<...> Yes 10,000,000 100 10 200% 100,000,000
FcsFastBTreeN<...> Yes 10,000,000 200 20 100% 50,000,000
SortedSet<...> Yes 10,000,000  1,230   123   16%  8,000,000
HashSet<...> No 10,000,000 47.3 4,73 422% 210,000,000
Dictionary<...> No 10,000,000 86.5 8,65 231% 115,000,000

 

MemoryStream generic class

FcsInmemStream<T> [where T : struct]

  • Methods: Append, Close, Length, Open, Position, Read, Seek, Write.

Source code

See the Github.

Benchmark

The benchmark was configured as follows:

  • CPU: Intel Xeon E3-1245 @ 3.3 GHz;
  • Windows 10, 64bit, .NET Standard 1.1
  • 4x4 GB DDR3 Kingston @ 1333 MHz
  • Append, Read, Write (cache 1,000 T) and foreach (cache 128 T)
FcsInmemStream<T> Append Read Write foreach
IOPS [T = 8 Byte] 160,000,000 800,000,000 800,000,000 80,000,000
IOPS [T = 16 Byte] 140,000,000 500,000,000 400,000,000 80,000,000
IOPS [T = 32 Byte] 90,000,000 280,000,000 280,000,000 70,000,000
IOPS [T = 64 Byte] 45,000,000 150,000,000 150,000,000 60,000,000
IOPS [T = 128 Byte] 20,000,000 75,000,000 50,000,000 33,000,000
IOPS [T = 256 Byte] 12,000,000 35,000,000 33,000,000 22,000,000
IOPS [T = 1024 Byte] 3,000,000 8,000,000 8,000,000 6,000,000
IOPS [T = 4096 Byte] 700,000 1,600,000 1,200,000 1,300,000

 　

INSTALL

Install via Nuget Package Manager

PM> Install-Package FriendlyCSharp.Databases

 

LICENSE

See the LICENSE.