TreeDb. Data structure
Here, after yesterday's discussion, and sketched an approximate structure of information storage:
Read more ...
Initially, a search is performed in the array of 2BIdx structures , which contains the structure from the first two bytes of the key name and the second value: the index of the directory array (Dir). In pic - this is the leftmost TB. tbl
In general, table 2BIdx is not needed, but its use speeds up the selection of Dir arrays.
The Dir key array is a list structure and has about the following fields:
- Key name
- pointer (or rather index) to the next element of the list
- pointer (as an option index) to the Node element
- nesting level.
')
The Dir key array has the dimension of 2 ^ 16 (65536) elements - if it is allowed by the language :(. Each array is dynamically allocated from the memory pool. The element number for all elements of the array is pass-through and is calculated as follows:
- the upper two bytes are the number of the Dir array,
- the lower two bytes - the index in the array.
all the keys in the array are sorted, so the pseudo-list structure is used (to minimize malloc).
Next, from the Dir structure, we get into the Node structure . All Node - are in the array of structures of 2 ^ 16 (65536) elements. The numbering of the elements of the structures is through, the algorithm for calculating the location of the node by index (# Node / index) is the same as in the Dir array
Node structure :
- index in the Dir array (backward link)
- Level nesting
- Next, index next node (brother)
- First - index on the first element of the nested structure
- pointer to the data and the length of the data.
Extraction of data occurs at. All data are piled up without separators. Knowing the Dinna and the address of the first byte of data, we easily “retrieve” from it and pass it on to processing.
If the data block is not enough, then there is a request for the next block.
I will try to implement such a scheme. Can anyone have any additional ideas?
Scaling ideas (oh, far to me before it): have a single Dir structure, according to my calculations, it should occupy about 2M in memory, in which the node address + server number is indicated (for example, the highest byte of the structure can be a number)
Read more ...
Initially, a search is performed in the array of 2BIdx structures , which contains the structure from the first two bytes of the key name and the second value: the index of the directory array (Dir). In pic - this is the leftmost TB. tbl
In general, table 2BIdx is not needed, but its use speeds up the selection of Dir arrays.
The Dir key array is a list structure and has about the following fields:
- Key name
- pointer (or rather index) to the next element of the list
- pointer (as an option index) to the Node element
- nesting level.
')
The Dir key array has the dimension of 2 ^ 16 (65536) elements - if it is allowed by the language :(. Each array is dynamically allocated from the memory pool. The element number for all elements of the array is pass-through and is calculated as follows:
- the upper two bytes are the number of the Dir array,
- the lower two bytes - the index in the array.
all the keys in the array are sorted, so the pseudo-list structure is used (to minimize malloc).
Next, from the Dir structure, we get into the Node structure . All Node - are in the array of structures of 2 ^ 16 (65536) elements. The numbering of the elements of the structures is through, the algorithm for calculating the location of the node by index (# Node / index) is the same as in the Dir array
Node structure :
- index in the Dir array (backward link)
- Level nesting
- Next, index next node (brother)
- First - index on the first element of the nested structure
- pointer to the data and the length of the data.
Extraction of data occurs at. All data are piled up without separators. Knowing the Dinna and the address of the first byte of data, we easily “retrieve” from it and pass it on to processing.
If the data block is not enough, then there is a request for the next block.
I will try to implement such a scheme. Can anyone have any additional ideas?
Scaling ideas (oh, far to me before it): have a single Dir structure, according to my calculations, it should occupy about 2M in memory, in which the node address + server number is indicated (for example, the highest byte of the structure can be a number)
Source: https://habr.com/ru/post/80988/
All Articles