Clustering

The easiest way to achieve good read performance is to partition a very large database into mutually exclusive groups of serial elements, where each group is characterised as follows

• The serial elements in a group are all closely related, meaning that when one serial element is read from disk, it is likely that other serial elements in the group will also be read in the near future.
• There is a tendency for the serial elements in a group to be written to the same segment. This is achieved by writing batches of related serial elements to the LSS at a time. As a corollary to this requirement, a group of related serial elements can't be so large that it defeats the whole idea of them being "clustered together".
• Every serial element in the group shares the same high 32 bits of the Serial element Id (Seid). This allows the LSS to achieve clustering in its internal hierarchical map used to track the physical locations of serial elements.

Over time there is an "increasing entropy" effect where related serial elements become spread around the disk. It can be very beneficial to recluster serial elements, particularly serial elements used to implement directory structures. This is achieved by occassionally rewriting all the relevant serial elements to the LSS in a single "batch".

Interestingly, it is the excellent write performance of the LSS, that makes it economical to recluster related data together. Therefore the LSS can also provide very competative read performance. Experiments have shown it to significantly outperform NTFS when reading or writing thousands of text files.