从这篇笔记开始,我们讲解有关数据库实现的相关概念和算法。本篇笔记主要记录数据库系统底层的物理存储结构,索引等相关概念。
数据库管理系统的数据操作算法、查询优化处理方法和事务处理算法与数据库的物理存储结构密切相关。在讨论物理存储结构时,我们不再关心应用程序员如何看待数据,而主要考虑如何在外存储器上以最优化的方式存放数据。物理存储结构的设计主要考虑数据库的操作效率、响应时间和空间利用率。
数据库通常存储在辅助存储设备上。
一次磁盘读写需要毫秒级的时间,和CPU/主存的速度相比非常慢,所以磁盘读写是数据库应用的瓶颈。数据库的物理存储结构,数据库操作算法和查询优化的研究都把最小化存盘读写次数作为重要目标之一。
主存和磁盘之间传送数据块时,使用缓冲区平衡两者的速度。
数据在磁盘上有多种存储方式,下面我们先不考虑实际使用中的情况,介绍几种可行的方案。
表示关系数据库中元组的属性值,如:姓名,年龄等。数据项具有类型,如integer等。
数据项的集合,对应于一个关系元组。按存储的记录数量可以分为定长纪录,非定长记录,按存储方法可以分为跨块存储(一个记录可以存储在多个文件块),非跨块存储。
记录的集合,一个文件块对应一个磁盘块,注意:概念上一个文件块不是对应文件系统上一个xxx.txt
,而是一个磁盘块。
记录随机存储在文件块中,新纪录存储在文件末尾,无序文件通常与索引一起使用,提升存取效率。
记录按某个域的值大小顺序排列。注:不一定是连续的。
索引是一种数据结构,通常是有序文件。索引记录称为索引项,存放索引域值和所在地址。索引记录通常按索引域排序。
索引文件可以形成多级索引。
主索引例子如图:
数据按主键值排序,主索引存储一个分组的第一条数据键值和磁盘块地址。
显然,主索引是稀疏索引。
聚集索引和主索引区别是索引域不是主键。
被索引域同样需要排序,聚集索引是稀疏索引。
辅助索引建立在文件的非排序域上,但辅助索引文件是有序文件。
显然这种索引是稠密索引。
文件被划分为n个hash桶,每个桶对应一个磁盘块,统一对记录的一个属性作hash,结果作为桶编号,通过桶编号,找到磁盘块地址。
hash冲突,最简单的办法是使用链表解决:
查询到某个链表时,只能遍历。
插入删除操作较为简单,这里就不叙述了。
Hash文件优点显而易见,这里看看它的缺点:hash桶数量不变,文件记录少时,会浪费大量存储空间,文件记录多时,链表很长,效率较差。
为了解决Hash桶数量不可变,我们介绍一种能够动态分配Hash桶的方案。该方案使用二叉树解决这个问题。
初始时只有一个hash桶B,B溢出时,就分成两个桶B1,B2,B中记录hash第一位为1的进入B1,为0的进入B2,B1或B2桶再次溢出就再根据hash值第二位次划分为两部分。
如图所示,最终形成了路径分为0-1的二叉树:
查询时,根据记录hash值的前几位,在树中搜索就可以找到对应的hash桶了。
我们还有一些其他的解决方案可以扩展Hash索引,这里再介绍一个将Hash索引数组翻倍的方式。
图中,每个Hash索引目录项指向一个Hash桶,我们假设一个桶能放4条记录,全局位深度为2表示我们取哈希值后两位建立索引表(当然不一定必须是后两位)。
现在在上图基础上,插入值d1,假设hash(d1)=0b1101,指向b桶,b桶未满,将d1插入b桶。
插入值d2,假设hash(d2)=10100,指向a桶,但是a桶满了,这时我们将a桶分裂为两个桶,其局部位深度+1,变为3,全局位深度也要+1,变为3,a桶中所有数据需要重新分配,Hash索引表由于多出一倍的长度,也要将新增的一半索引表的指向根据原表进行更新。
请参考数据结构相关章节。
推荐一个网址http://goneill.co.nz/btree-demo.php,里面可以演示B+树的插入删除等操作,不会的时候看一眼立刻就明白了。