Global Allocation Map、Shared
Global Allocation Map
有关区是否分配的信息。
Page Free Space 有关页分配和页的可用空间的信息。
Index Allocation Map 有关每个分配单元中表或索引所使用
的区的信息。
Bulk Changed Map 有关每个分配单元中自最后一条
BACKUP LOG 语句之后的大容量操
作所修改的区的信息。
Differential Changed Map 有关每个分配单元中自最后一条
BACKUP DATABASE 语句之后更改
的区的信息。
表1页中保存的数据类型
在数据页上,数据行紧接着页头(标头)按顺序放置;页头包含标识值,如页码或对象数据的对象ID;数据行持有实际的数据;
最后,页的末尾是行偏移表,对于页中的每一行,每个行偏移表都包含一个条目,每个条目记录对应行的第一个字节与页头的距
离,行偏移表中的条目的顺序与页中行的顺序相反。
图3数据页
索引的基本结构索引的基本结构
“索引(Index)提供查询的速度”这是对索引的最基本的解释,接下来我们将通过介绍索引的组成,让大家对索引有更深入的理
解。
索引是数据库中的一个独特的结构,由于它保存数据库信息,那么我们就需要给它分配磁盘空间和维护索引表。创建索引并不会
改变表中的数据,它只是创建了一个新的数据结构指向数据表;打个比方,平时我们使用字典查字时,首先我们要知道查询单词
起始字母,然后翻到目录页,接着查找单词具体在哪一页,这时我们目录就是索引表,而目录项就是索引了。
当然,索引比字典目录更为复杂,因为数据库必须处理插入,删除和更新等操作,这些操作将导致索引发生变化。
叶节点叶节点
假设我们磁盘上的数据是物理有序的,那么数据库在进行插入,删除和更新操作时,必然会导致数据发生变化,如果我们要保存
数据的连续和有序,那么我们就需要移动数据的物理位置,这将增大磁盘的I/O,使得整个数据库运行非常缓慢;使用索引的主
要目的是使数据逻辑有序,使数据独立于物理有序存储。
为了实现数据逻辑有序,索引使用双向链表的数据结构来保持数据逻辑顺序,如果要在两个节点中插入一个新的节点只需修改节
点的前驱和后继,而且无需修改新节点的物理位置。
双向链表(Doubly linked list)也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前
驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
理论上说,从双向链表中删除一个元素操作的时间复杂度是O(1),如果希望删除一个具体有给定关键字的元素,那么最坏的情况
下的时间复杂度为O(n)。
在删除的过程中,我们只需要将要删除的节点的前节点和后节点相连,然后将要删除的节点的前节点和后节点置为null即可。
代码如下:
//伪代码
node.prev.next=node.next;
node.next.prev=node.prev;
node.prev=node.next=null;