跳到主要内容

第六章 表的内存结构

简介​

数据库以一张张表存储数据。本文介绍表在内存中的组织方式。

内存结构​

表数据分成多层结构。从上到下， 第一层，由row group组成的二叉排序树。每个row group有122880行（120K）组成。 第二层，每个row group 由多个列的数据column data组成。每个列数据column data又由column segment组成的二叉排序树组成。 第三层，每个column segment对应一个内存连续block。block默认大小是256KB。每个column segment最多放置60个vector。vector在block上连续存储。 第四层，vector由2K个数据组成。为列存最小的运算、读写单元。

通俗理解， 先对表数据按行切成一个个row group。 每个row group 内部又按表的列切成一个个column segment。 每个column segment 再切成一个个vector。

为了支持MVCC，还需要事务版本数据。这里简要提一下，在讲事务时，再具体讲。 事务对行insert,delete时，列在逻辑上组成一行。行版本数据分成两层： 第一层，version node,记录在每个row group 上。每个row group一个。 第二层，chunk info 对应2048行版本数据。每个version node 由60个chunk info。

事务可以对不同的列进行不同的update。每个列column data记录列版本数据。列版本数据分成两层： 第一层：update node,记录在column data上。 第二层：update info 对应2048行版本数据。每个事务有单独的update info。不同事务的update info组成版本链表。每个update node由60个update info链表组成。

统计信息由null值、不同值个数、总数、最大最小值。每个列有独立的统计信息。分成三层： 第一层：表级别stats。记录每个列的stats. 记录row group集合上。 第二层：记录在每个column data上。整个column data的统计信息。 第三层：记录在每个column segment上。

简要逻辑结构：

表数据:
	row group 0;
	...
	row group i;
		column data 0;
		...
		column data j;
			column segment 0;
			...
			column segment k;
				vector 0;
				...
				vector 59;
				...
				update node 0;
				...
				update node x;
					update info list 0;
					...
					update into list 2047;
				...
				update node 59;
				stats ;
			...
			column segment o-1;
			stats;
		...
		column data m-1;
		...
		version node
			chunk info 0;
			...
			chunk info 59;
	...
	row group n-1;

数据结构​

表​

用DataTabe表示一表的内存结构。

  • 元信息：名称，列定义，约束，索引等
  • 数据载体：row group集合。

row group​

row group 按续拼接成表的数据。

row group集合RowGroupCollection存表的所有内存数据、版本数据和stats。

  • 总行数。表有多少行数据。
  • row group树。row group组成的二叉排序树。

row group树RowGroupSegmentTree存储所有的row group。

  • 按照每个row group的开始行号排序。

RowGroup

  • 记录连续的120K行数据。
  • 行版本信息
  • 每列数据
RowGroup {
	开始行 start
	列数据 []*ColumnData
	行版本信息 VersionNode
}

行版本信息VersionNode：


VersionNode{
	[60]ChunkInfo
}

ChunkInfo{
	开始行
	//vector info
	[2048]insert id
	[2048]delete id
}

column data​

column data逻辑表达一个row group内部某一列数据。

  • 元信息：开始行，数据类型等
  • column segment树。
  • 列版本信息

ColumnData {
	开始行 start
	type
	*ColumnSegmentTree
	列版本信息 *UpdateSegment
}

column segment树ColumnSegmentTree存储所有的column segment。

  • 按照开始行号排序

column segment

  • 元信息：类型、读写数据接口等
  • block信息：block id和offset
ColumnSegment{
	开始行
	type
	读写数据接口 CompressFunction
	BlockId
	Offset
}

列版本信息外层包装在UpdateSegment中：

  • 列版本信息。
  • 读写列版本信息的接口

实际版本信息记录在UpdateInfo

  • 版本号：事务ID
  • 操作记录
  • 链表指针
UpdateSegment{
	列版本信息 UpdateNode
}

UpdateNode{
	[60]UpdateNodeData
}

UpdateNodeData{
	版本信息 UpdateInfo
	操作的行号 []rowid
}

UpdateInfo{
	版本号
	操作记录；
	prev,next UpdateInfo
}

统计信息​

BaseStats记录zonemap、行数、不同值数。

在之上封装成SegmentStats记录column data和column segment的统计信息。

ColumnStats和TaleStats则是在表级别层面汇总的统计信息。记录在row group集合上。

DistinctStats统计不同值。

BaseStats{
	null值；
	不同值数；
	行数；
	minmax值
}

SegmentStats{
	BaseStats
}

TableStats{
	[]ColumnStats
}

ColumnStats{
	BaseStats
	DistinctStats
}

DistinctStats{
	hyperloglog
	count
}

小结​

简要介绍了表在内存中的数据组织方法。数据构成成分。引入概念row group、segment。