search

jankotek / mapdb

MapDB provides concurrent Maps, Sets and Queues backed by disk storage or off-heap-memory. It is a fast and easy to use embedded Java database engine.
https://mapdb.org
Apache License 2.0
4.89k stars 873 forks source link

Trying to understand how it works #1044

Open siddhsql opened 7 months ago

siddhsql commented 7 months ago

Hello! is there an explanation of how IndexTreeLongLongMap.kt works? I understand conceptually its a N-ary tree with N=128 and 4 levels. But things I don't understand are:

  1. What data is stored in the nodes of this tree?
  2. How do you manage that the tree only takes up space equal to actual elements in the tree not the upper fixed bound N^L?
  3. is there any well-known data structure that IndexTreeLongLongMap.kt maps to?

coming to the layout of data on the disk i.e., StoreDirect.kt, how is the data stored?

  1. is it stored in sorted order of the key?
  2. if so, then inserting elements in random key-order would impact the performance a lot as you will have to constantly reorder data on disk. is this indeed an issue?