什么是表的物理顺序和逻辑顺序?二者有何区别?

1、线性表的逻辑结构的基本特征

图2-1 线性表

线性结构是一个数据元素的有序(次序)集

1).集合中必存在唯一的一个“第一元素”；

2).集合中必存在唯一的一个“最后元素”

3).除最后元素之外,均有唯一的后继；

4).除第一元素之外,均有唯一的前驱.

2、线性表的顺序存储实现

顺序表是线性表的顺序存储结构.用一组地址连续的存储单元依次存储线性表的元素.

顺序表特点：

逻辑顺序与物理顺序一致

属随机存取的存储结构,即存取每个元素所花时间相等

假设线性表中每个元素需占用c个存储单元,计算结点存储地址公式：

LOC(ai+1)=LOC(ai)+c (1)

LOC(ai)=LOC(a1)+(i-1)*c (2)

顺序表上实现基本运算及时间复杂度分析.

1)插入算法：

假设在第 i 个元素之前插入的概率为 pi,则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行插入的概率都相等,则移动元素的期望值为：

插入算法的平均时间复杂性为 ,平均时间复杂性量级为O(n).

2)删除算法：

假设删除第 i 个元素的概率为qi ,则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为：

删除算法的平均时间复杂性为

,平均时间复杂性量级为O(n).

3、线性表的链式存储实现

链接实现线性表,可以克服顺序表的缺点.线性表的常见链式存储结构有：单链表、循环链表、双链表.

1)单链表

用一组地址任意的存储单元存放线性表中的数据元素.

元素(数据元素的映象)+ 指针(指示后继元素存储位置的) = 结点

链式存储特点：

逻辑顺序与物理顺序有可能不一致

属顺序存取的存储结构,即存取每个数据元素所花费的时间不相等

几种运算在单链表上的实现,包括：建立单链表、查找、插入、删除等.

2)循环链表

表中最后一个结点的指针域指向头结点,链表形成一个环.

特点：从表中任何一个结点出发可扫描整个链表中的所有结点.

3)双链表

特点:每个结点有两个指针域,克服单链表的单向性

注意：“插入”、“删除” *** 作,与单链表有很大不同.需要同时修改两个方向上的指针.

4、顺序表和链表的比较

空间性能比较、时间性能比较.

顺序存储结构：

优点：存储密度大、简单.数据元素的地址可以通过公式计算.

缺点：插入、删除 *** 作效率低,存储空间需要按最大需求事先分配,且要求一片连续的存储空间,容易造成浪费.

链式存储结构：

优点：存储空间按需分配；插入、删除 *** 作效率高.

缺点：链表中的结点需要存储指针,构造本身比顺序存储结构大.

时间复杂性量级

定位运算,顺序表和单链表,均为 O(n)

读表元：顺序表-O(1) (随机存取)单链表-O(n)

链入、删除：顺序表-0(n)单链表-O(1) (插入、删除方便)

A、聚集索引。

数据库表行中数据的物理顺序与键值的逻辑（索引）顺序相同。一个表只能有一个聚集索引，因为一个表的物理顺序只有一种情况，所以，对应的聚集索引只能有一个。

如果某索引不是聚集索引，则表中的行物理顺序与索引顺序不匹配，与非聚集索引相比，聚集索引有着更快的检索速度。

扩展资料：

聚集索引对于那些经常要搜索范围值的列特别有效。使用聚集索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻。

例如，如果应用程序执行的一个查询经常检索某一日期范围内的记录，则使用聚集索引可以迅速找到包含开始日期的行，然后检索表中所有相邻的行，直到到达结束日期。

这样有助于提高此类查询的性能。同样，如果对从表中检索的数据进行排序时经常要用到某一列，则可以将该表在该列上聚集（物理排序），避免每次查询该列时都进行排序，从而节省成本。

---