用双向链表实现数据库的逻辑连续

时间：2008-05-29 来源：剑心通明

摘要: 针对当前网络数据库存在的记录操作连续性的问题，本文利用双向链表的原理，避开了常规的思考方法，成功的实现了数据记录的逻辑连续，很好解决了记录操作连续性的问题。同时给出了用服务器端脚本PHP利用此原理操作MySql数据库的实例。

一问题的提出
信息就是数据，以提供信息和信息交互为主的网站必然离不开数据库的支持。比如常见的论坛、新闻发布系统都是完全基于数据库的，所有的程序提供给用户和管理者的只是一个操作界面，用户和管理者只要通过这个界面就可以实现对数据库中的数据进行添加，编辑和删除等操作。
对于数据库中的每条数据记录，我们都会给它加上一个唯一的标识(ID)以区别于其它的数据记录。为了方便用户对数据记录信息的查看和浏览，程序上往往提供给使用者可以直接从本条记录跳到下一条或上一条记录的功能。而这种功能正是基于ID的增加和减少来实现的。对于ID连续的数据记录这种功能的实现没有问题;然而，对于数据库中的一些数据被删除或丢弃后，相应的ID就不存在了，如果还使用这种方法就会出现大量空记录的问题。因此如何在ID不连续的情况在实现每条记录上下自由跳转，正是本文要解决的问题。目前，已经有一些解决这种问题的方法，常用的是每次出现数据记录ID不连续的时候，对数据进行再次排序，这种方法在数据量很大的时候系统的工作量是非常惊人的，这也是方法的最大缺陷。利用双向链表就避开了上面常规方法隐含的问题，并且不强求数据记录ID的连续，只是使它们在逻辑上的连续以达到我们的目的，下面就让我们先来看看双向列表的原理。

二双向链表的原理
在数据结构中，双向链表的存储结构如下图一所示:

图一
从上图我们可以看到，在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。其存储结构如下：

typedef struct DulNode{
struct DulNode *priou;
ElemType data;
struct DulNode *next;
}DulNode，*DuLinkList;

对指向双向链表任意结点的指针d，有下面的关系：

d->next->priou=d->priou->next=d

即：当前结点后继的前趋是自身，当前结点前趋的后继也是自身。
双向链表的删除操作原理: 先要搜索双向链表，查找要删除的节点X，为此引入节点P，若Data(P)=X，则删除X，同时修改其左节点的右指针和右节点的左指针，具体如图二：

图一
这种有效的方法，在对数据只进行了少量操作的情况下，保持了数据链表的完整连续性，这正是我们解决前面问题所希望的。下面我们就来看看利用此原理来解决问题的具体实现方法及实例。

三实现方法与实例演示
根据双向链表的原理，我们在组织数据库中的数据记录（数据项）时，可以将每条记录当作双向链表中的一个节点，不同记录之间的联系不是靠他们ID的大小顺序，而是通过两个指针分别指向上下记录节点。因此，我们必须在每个数据记录中定义三个属性:节点号ID，下一条记录节点号NEXT_ID，上一条记录节点号PRIOU _ID.这样程序调用数据记录进行上下记录切换的时候，不是简单的通过本身ID的加减来实现，而是通过自己的指针项来实现跳转。
如果需要删除某一项数据记录，只要同时修改上一条记录的NEXT_ID和下一条记录的PRIOU_ID，就可以继续保持所有数据记录的链接，这样就模拟了双向链表的指针功能，实现了数据项的逻辑连续。下面以目前比较流行的MySql数据库和PHP程序语言来具体实现上面的功能:
首先我们必须在MySql数据库建立测试用的数据库及数据表，其SQL语句定义如下:

CREATE DATABASE Test;
CREATE TABLE test (
ID int(30) DEFAULT '0' NOT NULL auto_increment，
Next_id int(30) DEFAULT '0' NOT NULL，
Priou_id int(30) DEFAULT '0' NOT NULL，
Data_title varchar(60) NOT NULL，
Data text NOT NULL，
KEY Id (Id)，
UNIQUE Id_2 (Id)
);

在此数据表中，我们定义所需要的链接指针外，还定义数据记录的标题(Data_title)和实际的数据(Data).下面给出实际操作此数据库的PHP代码段:

<?
//Date :2001/10/13
//Author: [email protected]
//注:加粗字体的为PHP函数库中定义的函数

$Dbname="Test";
$Tablename="test";
$my_link=mysql_connect('localhost'，'root'，''); //与数据库服务器建立连接
$db=mysql_select_db($Dbname，$my_link);

//插入数据的代码: Insert Data Code

/**** 执行插入数据操作，并且获取到ID ******/
$Insertquery="INSERT INTO $Tablename (Data_title，Data) VALUES('$datatitle'，'$data')";
$I_result=mysql_query($Insertquery) or die(mysql_error());
$id=mysql_insert_id(); //获得ID

/*****定义本记录的指针链接******/
$Priou_id=$id+1;
$Next_id=$id-1;
$Updatequery="UPDATE $Tablename SET Priou_id=$Priou_id，Next_id=$Next_id WHERE ID=".$id;
$U_result= mysql_query($Updatequery) or die(mysql_error());

//删除数据的操作代码:Detele Data Code

$id="n"; //即将被删除的某条数据记录的ID，根据具体情况获取

/*****获得当前要被删除记录的两个指针值*****/
$Selectquery2="SELECT * FROM $Tablename WHERE ID=".$id;
$S_result2= mysql_query($Selectquery2) or die(mysql_error());
$Priou_id=mysql_result($S_result2，0，"Priou_id");
$Next_id=mysql_result($S_result2，0，"Next_id");

/***** 更改上一条记录的右指针使其指向本记录的右指针***/
$UpdatePriouquery="UPDATE $Tablename SET Next_id=$Next_id WHERE ID=".$Priou_id;
$UP_result= mysql_query($UpdatePriouquery) or die(mysql_error());
/***** 更改下一条记录的左指针使其指向本记录的左指针***/
$UpdateNextquery="UPDATE $Tablename SET Priou_id=$Priou_id WHERE ID=".Next_id;
$UN_result= mysql_query($UpdateNextquery) or die(mysql_error());

/******执行删除操作*******/
$Deletequery="DELETE FROM $Tablename WHERE ID=".$id;
$D_result= mysql_query($Deletequery) or die(mysql_error());

mysql_close();
?>

本代码在Win98+Apache+Mysql 1.3.14+PHP4.0.1p12下运行通过，指着是功能和语言，读者如果要引用需要将插入功能代码和删除功能代码分开引用。同时，本代码只是基本功能的演示，更多异常情况如首记录指针问题需要大家自己去处理。
通过上面的例子，大家可以很清楚看到只要在每次删除记录前，将其连后记录链接起来，由于记录的跳转目的地是记录本身的链接指针决定的，所以保持了数据的连续性，这正是双向链表的优势所在。这样只需要少量的编程代码就节约了系统的大量时间，笔者希望这种有效的实现方法能得到更多的实际应用。