iotdb icon indicating copy to clipboard operation
iotdb copied to clipboard

[IOTDB-3216]Refactor Segments in SchemaFile to B+ Tree structure from list structure

Open bigreybear opened this issue 3 years ago • 0 comments

Background

Children of the same node on MTree will be stored into one or several linked segments in SchemaFile when Main Memory wears out after #4732 merged . These segments are linked like a list, which turned out poor performance when number of children surged.

What's Different

This PR reshape the structure between segments which share parent node on MTree to a B+ Tree (both with name and alias), which should improve the performace even with tremendous number of children on one node.

Besides, this PR puts foward a primary framework named PageManager which decouples SchemaPage management from SchemaFile and makes it more reasonable to implement different structure between SchemaPages.

And the structure this PR implemented is a bit different from a classical B+ Tree in 2 ways:

  1. A node on this structure may split into 2 part with different number of entries, which is up to the trend of the insertion;
  2. The split may take a bulk way if the key of the newly insert is the biggest or smallest of the original node, which may help to improve a little.

SchemaFileClassDiagram drawio (1)

A detailed specification for diagram above: https://apache-iotdb.feishu.cn/docs/doccnJHlbakm1n3GN6uLU6rz8Zm

bigreybear avatar May 20 '22 12:05 bigreybear