| 主权项 |
1.一种面向列存储DWMS的B+树索引方法，其特征在于，步骤为：步骤1、列数据生成：导入用户数据，将原始按行存储的数据垂直划分为单列，为每一列的每一项数据根据其所在的行号，添加用于元组重建的行号项，形成二元组(行号，列值)，申请数据段，将新产生的每列值数据保存在一个数据段中；步骤2、若B+树关键字为行号数据，则转向步骤4进行创建；若B+树关键字为列值数据，转步骤3首先对列值进行排序；步骤3、将多路归并和堆排序组合使用对列值数据进行排序，所述步骤3包括：步骤3.1、初始化：在内存中申请一个排序区，其大小记为K，令K是待排序的数据块大小的整数倍，若待排序数据块数Blk_num>K，将采用多路归并外排序的方法，归并时的子列表个数为M，令<img file="FDA0000442824400000011.GIF" wi="429" he="71" />每个待归并的子列表内块数D=Blk_num／M，读取数据段中源数据，把数据块二元组中的列值数据拆分出来，装入数组，放入排序区，使用堆排序算法将数组作为输入参数，对数组进行排序；若Blk_num<=K，则排序结束；否则，把排好序的数据项重新组装成数据块，写回临时段中；步骤3.2、对N个临时段进行归并排序；步骤4、B+树索引初始化；步骤5、创建B+树叶子结点：申请B+树的叶子结点，将数据项直接填充入叶子结点得到数据块，构成B+树第0层；步骤6、产生中间结点：由下至上迭代建立B+树的中间层结点直到整棵B+树创建结束，其步骤为：步骤6.1、生成索引项，索引项为由下一层索引块中的第一个列值、对应的行号以及该索引块的块号构成的三元组；步骤6.2、判断列值类型是定长数据或变长数据，若是定长列值，计算得到索引项的长度，进而可得索引块中的索引项个数=索引块空间大小／索引项长度，第一层中的索引块个数=第0层中的数据块个数／每个结点中的索引项个数，申请索引块空间，将索引项批量插入到索引块中；若是变长列值，先申请一个索引块，然后依次插入三元组，直到放不下时才申请新的索引块；步骤6.3、一层创建完成后，转向步骤6.1，按照同样的过程创建上一层中间结点，直到整棵B+树创建结束。 |
