Skip to content

Sparse containers based on adaptive radix tree

License

Notifications You must be signed in to change notification settings

fyfrey/d-art-containers

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

28 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

d-art-containers

My implementation of sparse array based on adaptive radix tree(ART) using Dlang. Also planed sparse bit set.

It is based on this article http://www-db.in.tum.de/~leis/papers/ART.pdf

And here is general information about radix tree: https://en.wikipedia.org/wiki/Radix_tree

Radix tree uses node with N = "Radix" children. For this iplementation Radix == 256(byte capacity). Each byte of a key for the container corresponds one level of the tree (tree haight is equal to size of the key). Also radix tree doesn't store keys of the data explicitly. A key can be restored on the path to the leaf.

ART uses several optimizations few of wich currently implemented:

  • Adaptive node size: there are Node4, Node16,Node48, Node256 with different strategies to store elements (implemented). Note: In a NodeX, X is a capacity of the node.
  • Collapsing nodes. Nodes with one child does not explixitly created. Only their keys stored. (implemented)
  • SIMD optimisations for fast access in nodes other then Node256. (not implemented).

Also implemented range over container. TODO list for ranges:

  • Slices from key to key.
  • Removing element at the begin(end).

Interface implementation:

  • byUbytes/byOrderedUbytes (decomposes typed key by ubytes)
    • for uints
    • ints
    • floats/doubles
    • structures
    • objects
    • strings
    • arrays (static and dynamic)

MultiRadix nodes (possible optimisation not used in base ART): Radix treas are slow for random insertions. To improve it try to use node like SmallNode but with bigger keys (ushort, uint).

About

Sparse containers based on adaptive radix tree

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • D 100.0%