文章目录
1、基本概念2、文件组织2.1 定长记录2.2 变长记录2.3 文件中记录的组织3 缓冲区1、基本概念
1、内存数据库与磁盘数据库的特征比较
2、LRU: Least Recently Used,该算法的设计原则是,如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小,也就是说,当限定的空间已经存满数据时,应当把最久没有被访问到的数据淘汰。
2、文件组织
一个数据库被映射到多个不同的文件,这些文件由底层的操作系统来维护。文件在逻辑上是数据记录的集合,文件的结构取决于所属的文件系统。
块(block)是数据在文件中存储和读取的基本单元,其大小固定,大多数数据库默认使用 4~8KB 的块大小,在创建数据库实例时,有些数据库允许指定块的大小,要根据数据的特征来决定多个的块更合理。
一个块可能包含多条记录,对于大数据,比如图片,视频等,比块要大得多,需要单独存储,并在记录中保存指向大数据的指针。
每条记录都存储在相同的块中,不能一部分在 A 块中,另一部分在 B 块中,这样的设计能简化并加速数据访问。
关系型数据库中,不同表的记录通常具有不同的大小,这时数据库可以选择映射到多个文件中,同一文件中只存储固定长度的记录;也可以构建特殊的文件,支持容纳不定长度的记录。很显然,后者实现起来更复杂。
2.1 定长记录
定长记录占用固定大小的存储空间,管理上比较简单,有两点需要注意:
单条记录不能跨块
存储,一个块上只能存储整数个记录;文件中的记录是连续存储的,在删除记录后,需要对剩余的记录进行整理,不然会出现大量零碎的空闲空间。
记录整理大体有两个方向:
移动填充:当删除记录时,移动剩余的记录,使存储保持连续;可以把后续的记录往前移,使文件中存储的记录依然保持连续;也可以把最后一个移过来,填充删除的记录所在的位置。空闲列表:在文件头维护一个空闲列表,在删除记录时,将其所在的位置添加到空闲列表中,在下一个记录插入时再填充。
对定长记录文件的插入和删除是容易实现的,因为被删除记录留下的可用空间恰好是插入记录所需的空间。
2.2 变长记录
数据库文件中使用变长记录的场景:
多种记录类型在一个文件中存储;允许一个或多个字段是变长的记录类型;允许可重复字段的记录类型,例如数组或多重集合;
实现变长记录需要解决两个问题:
如何存取块中的记录:在块中如何存储变长记录,使得块中的记录可以轻松地抽取;如何存取记录中的属性:如何描述一条记录,使得单个属性可以轻松地抽取;
.
1、下面是一条变长记录,它包含了四个部分;
空值位图用来表示记录中的按个属性是空值,0000
表示四个属性都不为空,0010
表示第三个属性的值为空。这里需要注意,空值位图之前的部分为记录的定长部分
,无论哪个属性为空,这个结构的大小从始至终都是不变的,当某个属性为空值时,只表明可以忽略其所对应的定长部分
对应的值。
也有一些设计中,空值位图存储在记录的开头,并且对空属性不存储数据(值或偏移量/长度),这种方式是典型的时间换空间
设计,对于稀疏型记录比较有效。
2、分槽的页结构(slotted-page structure)一般用于在块中组织记录:
分槽页结构
是变长记录
的存储管理技术中的一种,用于在块中组织记录。
每个块的开始处有一个块头,块头中包含的信息有:
块头中已经存储的记录的条目个数;块中空闲空间的末尾地址;条目数组,每个条目中存储了该条目所对应变长记录的大小和地址;
记录在块中是从后往前连续存储的,空闲空间
处于块头
和记录
之间,当插入新的记录时,记录的(大小,位置)
对应的entry
添加到块头的末尾,记录本身的值添加空闲空间的末尾。
2.3 文件中记录的组织
文件中记录组织的几种方式:
堆文件组织(heap file organization):一条记录可以放在文件中的任何地方,只要那个地方有空间存放这条记录,记录是没有顺序的,通常每个关系使用一个单独的文件。顺序文件组织(sequential file organization):记录根据其search key
的值顺序存储。散列文件组织(hashing file organization): 在每条记录的某些属性上计算一个散列函数,散列的结果确定了记录应放到文件的哪个块中。
通常,每个关系的记录用一个单独的文件存储,但是在多表聚簇文件组织(multitable clustering file organization)中,几个不同关系的记录存储在同一个文件中,而且,不同关系的相关记录存储在相同的块中,这样一个 I/O 操作可以从所有关系中取到相关的记录。