死鎖的發生對系統的性能和吞吐量都有重要影響，經檢測發現，管理信息系統的死鎖主要是因為兩個或多個線程（登錄）搶占同一表數據資源。引起長時間搶占同一資源不是因為我們需要處理的事務太復雜，時間太長，而往往是因為我們在前端應用程序對數據庫作操作時忘了提交。本文介紹一種處理解決這種死鎖的方法。

Sybase封鎖原理

數據共享與數據一致性是一對不可調和的矛盾，為了達到數據共享與數據一致，必須進行并發控制。并發控制的任務就是為了避免共享沖突而引起的數據不一致。Sybase SQL Server并發控制的方法是加鎖機制（LOCKING）.

鎖的類型

Sybase SQL Server有三種封鎖類型：排它鎖（exclusive lock,簡稱X鎖）；共享鎖（share lock,簡稱S鎖）；更新鎖（update lock,簡稱U鎖）。這三種鎖的相容矩陣表如下：

×:表示不兼容。∨：表示兼容。

Sybase SQL Server是自動決定加鎖類型的。一般來說，讀（SELECT）操作使用S鎖，寫（UPDATE,INSERT和delete）操作使用X鎖。U鎖是建立在頁級上的，它在一個更新操作開始時獲得，當要修改這些頁時，U鎖會升級為X鎖。

鎖的力度

SQL Server有兩級鎖：頁鎖和表鎖。通常頁鎖比表鎖的限制更少（或更小）。頁鎖對本頁的所有行進行鎖定，而表鎖則鎖定整個表。為了減小用戶間的數據爭用和改進并發性，SQL Server試圖盡可能地使用頁鎖。

當SQL Server決定一個語句將訪問整個表或表的大多數頁時，它用表鎖來提供更有效的鎖定。鎖定策略直接受查詢方案約束，如果update或delete語句沒有可用的索引，它就執行表掃描或請求一個表鎖定。如果update或delete語句使用了索引，它就通過請求頁鎖來開始，如果影響到大多數行，它就要請求表鎖。一旦一個語句積累的頁鎖超過鎖提升閾值，SQL Server就設法給該對象分配一個表鎖。如果成功了，頁鎖就不再必要了，因此被釋放。表鎖也在頁層提供避免鎖沖突的方法。對于有些命令SQL Server自動使用表鎖。

鎖的狀態

SQL SERVER加鎖有三種狀態：

1）意向鎖（intend）—是一種表級鎖，它表示在一個數據頁上獲得一個S或X鎖的意向。意向鎖可以防止其他事務在該數據頁的表上獲得排它鎖。

2）阻塞（blocking,簡記blk）—它表明目前加鎖進程的狀態，帶有blk后綴的鎖說明該進程目前正阻塞另一個需要獲得鎖的進程，只有這一進程完成，其他進程才可以進行。

3）需求鎖（demand）—表示此時該進程企圖得到一個排它鎖。它可以防止在這一表或頁上加過多的S鎖，她表示某一事務是下一個去鎖定該表和該頁的事務。

需求鎖是一個內部過程，因此用sp_lock是無法看見的。

死鎖DEADLOCK

簡單地說，有兩個用戶進程，每個進程都在一個單獨的頁或表上有一個鎖，而且每個進程都想在對方進程的頁或表上請求不相容鎖時就會發生“死鎖”。在這種情況下，第一個進程在等待另一進程釋放鎖，但另一進程要等到第一個進程的對象釋放時才會釋放自己的鎖。

SQL Server檢查是否死鎖，并終止事務中CPU時間積累最小的用戶（即最后進入的用戶）。SQL Server回滾該用戶的事務，并用消息號1205通知有此死鎖行為的應用程序，然后允許其他用戶進程繼續進行。

在多用戶情形下，每個用戶的應用程序都應檢查每個修改數據的事務是否有1205號消息，以此確定是否有可能死鎖。消息號1025表示該用戶的事務因死鎖而終止并被回滾。應用程序必須重新開始這個事務處理。

查找死鎖原因

既然管理信息系統長時間死鎖的原因是由于我們提交或者是提交不當，那么我們就可以通過修改程序防止出現死鎖。定位死鎖出錯處主要經過以下三步：

1）在死鎖出現時，用SP_WHO,SP_LOCK獲得進程與鎖的活動情況。
2）結合庫表sysobjects和相應的操作員信息表查出被鎖的庫表與鎖住別人的操作員。
3）根據鎖定的庫表與操作員的崗位，可以估計出程序大約出錯處。詢問操作員在死鎖時執行的具體操作即可完全定位出錯處。最后查找程序并修改之。

用sp_who獲取關于被阻礙進程的信息

系統過程sp_who給出系統進程的報告。如果用戶的命令正被另一進程保持的鎖阻礙，則：
◆status列顯示“lock sleep”。
◆blk列顯示保持該鎖或這些鎖的進程標識，即被誰鎖定了。
◆loginame列顯示登錄操作員。結合相應的操作員信息表，便可知道操作員是誰。
Fid spid status loginame origname blk dbname cmd
0 1 lock sleep lm lm 18 QJYD SELECT
0 2 sleeping NULL NULL 0 master NETWORK HANDLER
0 3 sleeping NULL NULL 0 master NETWORK HANDLER
……

用sp_lock瀏覽鎖
要得到關于當前SQL Server上保持的鎖的報告，可用系統過程sp_lock [spid1[,spid2]]，spid1,spid2是表master.dbo.sysprocesses中的sql server進程id號，用sp_who可以得到鎖定與被鎖定的spid號：

◆locktype列顯示加鎖的類型和封鎖的粒度，有些鎖的后綴還帶有blk表明鎖的狀態。前綴表明鎖的類型：Sh—共享鎖，Ex—排它鎖或更新鎖，中間表明鎖死在表上（”table”或’intent’）還是在頁上（page）. 后綴“blk”表明該進程正在障礙另一個需要請求鎖的進程。一旦正在障礙的進程一結束，其他進程就向前移動。“demand”后綴表明當前共享鎖一釋放， 該進程就申請互斥鎖。

◆table_id列顯示表的id號，結合sysobjects即可查出被封鎖的表名。

執行該進程后屏幕顯示

Fid Spid locktype table_id page row dbname Class context
0 1 Sh_intent 678293476 0 0 QJYD Non Cursor LockFam dur
0 1 Sh_page 678293476 31764 0 QJYD Non Cursor Lock
0 18 Ex_intent 9767092 0 0 QJYD Non Cursor LockFam dur
……

定位出錯處

根據sp_who與sp_lock命令的結果，結合sysobjects和相應的操作員信息表。得到操作員及其在死鎖時所操作的庫表，便大約可以知道應用程序的出錯處，再詢問操作員在死鎖時執行什么操作以進一步認證。最后查找程序并修正之。


附:
鎖的問題一般來講是這樣的  
   
  首先判斷是否存在鎖競爭  
   
  1、基于系統管理員的經驗找出熱點表  
   
  2、通過以下方法判斷：  
   
  sp_who  
  察看系統中是否有status為lock   sleep的用戶。如果存在，再運行命令  
  sp_lock  
  察看系統中被鎖住的表的table_id  
  繼續運行命令  
  select   *   from   sysobjects   where   id   =   table_id  
  找到被鎖住的表名。  
  如果發現sp_who中有多個用戶被鎖，那么，就可認為是鎖造成了數據庫系統的性能底下。  
   
  調優方法1：修改對應表的加鎖模式由allpages為行級鎖，如：  
  alter   table   XXXX   lock   datarows  
   
  調優方法2：改大環境參數number   of   locks，如：  
  sp_configure   “number   of   locks”,   50000  
  注意，在這種情況下需要保持total   memory與number   of   locks的匹配性。  
   
  調優方法3：配置鎖提升閾值，可修改的配置包括兩項內容：  
  Page(HWM)、Row(HWM)，命令如下：  
   
  Sp_configure   ‘page   lock   promotion   HWM’,   500  
  Sp_configure   ‘row   lock   promotion   HWM’,   500  

sp_who報告的狀態值

狀態          表示       kill命令的效果

recv sleep  等待網絡讀取  立即
send sleep  等待網絡發送  立即
alarm sleep 等待警報      立即
lock sleep  等待獲取鎖    立即
sync sleep  等待同系列另一進程的同步消息   立即.系列中的其它進程也必須變為可注銷的狀態
sleeping    等待磁盤I/O或某種其它資源.或許表示正在運行的進程,但正在執行大量的磁盤I/O  少數休眠進程不能蘇醒,因而需要服務器重啟以將其清除.
runnable    在可運行進程隊列中       立即
running     活躍地運行在一個服務器引擎中  立即
infected    服務器已檢測到嚴重的錯誤情況;極其少見    不要使用kill命令.可能需要重啟服務器以清除進程.
background  由Adaptive Server而不是用戶進程運行的進程例如閾值過程   立即;使用kill時必須極其小心.建議在注銷背景進程之前,仔細檢查sysprocesses
log suspend   到達日志的最后機會閾值時掛起的進程   立即

參考<sybase數據庫系統管理指南>

 ---★ 本文轉摘自『onlyhot blog ※ blog.onlyhot.cn』http://www.onlyhot.cn/blog/?action=show&id=1178

共享鎖

sp_getapplock 鎖定應用程序資源

sp_releaseapplock 為應用程序資源解鎖

SET LOCK_TIMEOUT 1800 鎖超時期限設置

sp_configure 'deadlock checking period',5000 設置鎖檢測周期

sp_configure 'lock wait period',5000 設置鎖的等待時間

sp_setrowlockpromote 設置基本個表的最大行鎖升級數(鎖數)

sp_setrowlockpromote 'TABLE',TREECODE,500,500,100

sp_setrowlockpromote 'TABLE',LCD05,500,500,100

[Lock Manager]

number of locks = 50000 #鎖數

deadlock checking period = DEFAULT

freelock transfer block size = DEFAULT

max engine freelocks = DEFAULT

lock spinlock ratio = DEFAULT

lock hashtable size = DEFAULT

lock scheme = DEFAULT

lock wait period = DEFAULT

read committed with lock = DEFAULT

當很多事務同時訪問同一個數據庫時，會加劇鎖資源爭奪，嚴重時事務之間會發生死鎖。可用sp_object_stats查明死鎖位置。該過程報告資源爭奪最激烈的10張表、一個數據庫中資源爭奪的表和單個表的爭奪情況。語法為sp_object_stats interval [, top_n [, dbname [, objname [, rpt_option ]]]]，查看鎖爭奪情況只需設置interval為“hh:mm:ss”。如果顯示每種鎖的爭奪程度超過15%，應該改變加鎖方式，比如表的全頁鎖改成數據頁鎖，數據頁鎖改成數據行鎖等。

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

allow remote access 1 0 1 1

print recovery information 0 0 0 0

recovery interval in minutes 5 0 5 5

tape retention in days 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

global async prefetch limit 10 0 10 10

global cache partition number 1 0 1 1

memory alignment boundary 2048 0 2048 2048

number of index trips 0 0 0 0

number of oam trips 0 0 0 0

procedure cache percent 20 22426 20 20

total data cache size 0 89698 0 89698

total memory 47104 196608 98304 98304

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

cis bulk insert batch size 0 0 0 0

cis connect timeout 0 0 0 0

cis cursor rows 50 0 50 50

cis packet size 512 0 512 512

cis rpc handling 0 0 0 0

enable cis 1 0 1 1

max cis remote connections 0 0 0 0

max cis remote servers 25 19 25 25

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

dtm detach timeout period 0 0 0 0

dtm lock timeout period 300 0 300 300

enable xact coordination 1 0 1 1

number of dtx participants 500 149 500 500

strict dtm enforcement 0 0 0 0

txn to pss ratio 16 3692 16 16

xact coordination interval 60 0 60 60

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

average cap size 200 0 200 200

caps per ccb 50 0 50 50

dump on conditions 0 0 0 0

maximum dump conditions 10 0 10 10

number of ccbs 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

allow sql server async i/o 1 0 1 1

disable disk mirroring 0 0 0 0

disk i/o structures 256 31 256 256

number of devices 10 #5 10 10

page utilization percent 95 0 95 95

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

event log computer name LocalSystem 0 LocalSystem LocalSystem

event logging 1 0 1 1

log audit logon failure 0 0 0 0

log audit logon success 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

esp execution priority 8 0 8 8

esp execution stacksize 77824 0 77824 77824

esp unload dll 0 0 0 0

start mail session 0 0 0 0

xp_cmdshell context 1 0 1 1

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

configuration file 0 0 0 /sybase/hgd

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

enable java 0 0 0 0

size of global fixed heap 300 0 300 300

size of process object heap 300 0 300 300

size of shared class heap 3072 0 3072 3072

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

default character set id 1 0 1 1

default language id 0 0 0 0

default sortorder id 50 0 50 50

disable character set conversi 0 0 0 0

enable unicode conversions 0 0 1 1

number of languages in cache 3 4 3 3

size of unilib cache 0 140 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

deadlock checking period 500 0 500 500

freelock transfer block size 30 0 30 30

lock address spinlock ratio 100 0 100 100

lock hashtable size 2048 48 2048 2048

lock scheme allpages 0 allpages allpages

lock spinlock ratio 85 0 85 85

lock table spinlock ratio 20 0 20 20

lock wait period 2147483647 0 2147483647 2147483647

max engine freelocks 10 0 10 10

number of locks 5000 2344 10000 10000

print deadlock information 0 0 1 1

read committed with lock 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

additional network memory 0 0 0 0

allow resource limits 0 0 0 0

audit queue size 100 42 100 100

average cap size 200 0 200 200

caps per ccb 50 0 50 50

deadlock pipe max messages 0 0 0 0

default network packet size 512 #505 512 512

disk i/o structures 256 31 256 256

enable rep agent threads 0 0 0 0

errorlog pipe max messages 0 0 0 0

event buffers per engine 100 #11 100 100

executable codesize + overhead 0 20261 0 20261

lock hashtable size 2048 48 2048 2048

lock spinlock ratio 85 0 85 85

max cis remote servers 25 19 25 25

max number network listeners 5 868 5 5

max online engines 1 216 1 1

max roles enabled per user 20 #22 20 20

memory per worker process 1024 0 1024 1024

number of alarms 40 3 40 40

number of aux scan descriptors 200 #258 200 200

number of ccbs 0 0 0 0

number of devices 10 #5 10 10

number of languages in cache 3 4 3 3

number of large i/o buffers 6 97 6 6

number of locks 5000 2344 10000 10000

number of mailboxes 30 1 30 30

number of messages 64 3 64 64

number of open databases 12 1239 12 12

number of open indexes 500 512 500 500

number of open objects 500 561 500 500

number of remote connections 20 86 50 50

number of remote logins 20 23 20 20

number of remote sites 10 1729 10 10

number of user connections 25 43141 250 250

number of worker processes 0 0 0 0

partition groups 1024 904 1024 1024

permission cache entries 15 #227 15 15

plan text pipe max messages 0 0 0 0

procedure cache percent 20 22426 20 20

process wait events 0 0 0 0

remote server pre-read packets 3 #83 3 3

size of global fixed heap 300 0 300 300

size of process object heap 300 0 300 300

size of shared class heap 3072 0 3072 3072

size of unilib cache 0 140 0 0

sql text pipe max messages 0 0 0 0

stack guard size 4096 #1108 4096 4096

stack size 86016 #23269 86016 86016

statement pipe max messages 0 0 0 0

total data cache size 0 89698 0 89698

total memory 47104 196608 98304 98304

txn to pss ratio 16 3692 16 16

wait event timing 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

number of open databases 12 1239 12 12

number of open indexes 500 512 500 500

number of open objects 500 561 500 500

open index hash spinlock ratio 100 0 100 100

open index spinlock ratio 100 0 100 100

open object spinlock ratio 100 0 100 100

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

Q diagnostics active 0 0 0 0

SQL batch capture 0 0 0 0

deadlock pipe active 0 0 0 0

deadlock pipe max messages 0 0 0 0

errorlog pipe active 0 0 0 0

errorlog pipe max messages 0 0 0 0

object lockwait timing 0 0 0 0

per object statistics active 0 0 0 0

plan text pipe active 0 0 0 0

plan text pipe max messages 0 0 0 0

process wait events 0 0 0 0

sql text pipe active 0 0 0 0

sql text pipe max messages 0 0 0 0

statement pipe active 0 0 0 0

statement pipe max messages 0 0 0 0

statement statistics active 0 0 0 0

wait event timing 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

additional network memory 0 0 0 0

allow remote access 1 0 1 1

allow sendmsg 0 0 0 0

default network packet size 512 #505 512 512

max network packet size 512 0 512 512

max number network listeners 5 868 5 5

number of remote connections 20 86 50 50

number of remote logins 20 23 20 20

number of remote sites 10 1729 10 10

remote server pre-read packets 3 #83 3 3

syb_sendmsg port number 0 0 0 0

tcp no delay 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

max async i/os per engine 2147483647 0 2147483647 2147483647

max async i/os per server 2147483647 0 2147483647 2147483647

o/s file descriptors 0 0 0 1024

tcp no delay 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

max parallel degree 1 0 1 1

max scan parallel degree 1 0 1 1

memory per worker process 1024 0 1024 1024

number of worker processes 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

additional network memory 0 0 0 0

lock shared memory 0 0 0 0

max SQL text monitored 0 7 0 0

shared memory starting address 0 0 0 0

total memory 47104 196608 98304 98304

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

max online engines 1 216 1 1

min online engines 1 0 1 1

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

enable rep agent threads 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

SQL Perfmon Integration 1 0 1 1

abstract plan cache 0 0 0 0

abstract plan dump 0 0 0 0

abstract plan load 0 0 0 0

abstract plan replace 0 0 0 0

allow backward scans 1 0 1 1

allow nested triggers 1 0 1 1

allow resource limits 0 0 0 0

allow updates to system tables 0 0 1 1

audit queue size 100 42 100 100

cpu accounting flush interval 200 0 200 200

cpu grace time 500 0 500 500

deadlock retries 5 0 5 5

default database size 2 0 2 2

default exp_row_size percent 5 0 5 5

default fill factor percent 0 0 0 0

enable DTM 0 0 0 0

enable HA 0 0 0 0

enable housekeeper GC 1 0 1 1

enable sort-merge join and JTC 0 0 0 0

event buffers per engine 100 #11 100 100

housekeeper free write percent 1 0 1 1

i/o accounting flush interval 1000 0 1000 1000

i/o polling process count 10 0 10 10

identity burning set factor 5000 0 5000 5000

identity grab size 1 0 1 1

license information 25 0 25 25

number of alarms 40 3 40 40

number of aux scan descriptors 200 #258 200 200

number of large i/o buffers 6 97 6 6

number of mailboxes 30 1 30 30

number of messages 64 3 64 64

number of open databases 12 1239 12 12

number of open indexes 500 512 500 500

number of open objects 500 561 500 500

number of pre-allocated extent 2 0 2 2

number of sort buffers 500 0 500 500

page lock promotion HWM 200 0 200 200

page lock promotion LWM 200 0 200 200

page lock promotion PCT 100 0 100 100

partition groups 1024 904 1024 1024

partition spinlock ratio 10 0 10 10

print deadlock information 0 0 1 1

row lock promotion HWM 200 0 200 200

row lock promotion LWM 200 0 200 200

row lock promotion PCT 100 0 100 100

runnable process search count 2000 0 2000 2000

size of auto identity column 10 0 10 10

sql server clock tick length 100000 0 100000 100000

text prefetch size 16 0 16 16

time slice 100 0 100 100

upgrade version 1100 0 12000 12000

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

allow procedure grouping 1 0 1 1

auditing 0 0 0 0

check password for digit 0 0 0 0

curread change w/ open cursors 1 0 1 1

current audit table 1 0 1 1

max roles enabled per user 20 #22 20 20

maximum failed logins 0 0 0 0

minimum password length 6 0 6 6

msg confidentiality reqd 0 0 0 0

msg integrity reqd 0 0 0 0

secure default login guest 0 guest guest

select on syscomments.text 1 0 1 1

suspend audit when device full 1 0 1 1

unified login required 0 0 0 0

use security services 0 0 0 0

Parameter Name Default Memory Used Config Value Run Value

-------------- ------- ----------- ------------ ---------

default network packet size 512 #505 512 512

number of pre-allocated extent 2 0 2 2

number of user connections 25 43141 250 250

permission cache entries 15 #227 15 15

stack guard size 4096 #1108 4096 4096

stack size 86016 #23269 86016 86016

systemwide password expiration 0 0 0 0

user log cache size 2048 0 2048 2048

user log cache spinlock ratio 20 0 20 20

無論你要構建自己的論壇，在你的網站上發布消息還是書寫自己的cms [1]程序，你都會遇到要在數據庫中存儲層次數據的情況。同時，除非你使用一種像XML [2]的數據庫，否則關系數據庫中的表都不是層次結構的，他們只是一個平坦的列表。所以你必須找到一種把層次數據庫轉化的方法。

存儲樹形結構是一個很常見的問題，他有好幾種解決方案。主要有兩種方法：鄰接列表模型和改進前序遍歷樹算法

在本文中，我們將探討這兩種保存層次數據的方法。我將舉一個在線食品店樹形圖的例子。這個食品店通過類別、顏色和品種來組織食品。樹形圖如下：

本文包含了一些代碼的例子來演示如何保存和獲取數據。我選擇PHP [3]來寫例子，因為我常用這個語言，而且很多人也都使用或者知道這個語言。你可以很方便地把它們翻譯成你自己用的語言。

鄰接列表模型(The Adjacency List Model)

我們要嘗試的第一個——也是最優美的——方法稱為“鄰接列表模型”或稱為“遞歸方法”。它是一個很優雅的方法因為你只需要一個簡單的方法來在你的樹中進行迭代。在我們的食品店中，鄰接列表的表格如下：

如你所見，對每個節點保存一個“父”節點。我們可以看到“Pear [4]”是“Green”的一個子節點，而后者又是“Fruit”的子節點，如此類推。根節點，“Food”，則他的父節點沒有值。為了簡單，我只用了“title”值來標識每個節點。當然，在實際的數據庫中，你要使用數字的ID。

顯示樹

現在我們已經把樹放入數據庫中了，得寫一個顯示函數了。這個函數將從根節點開始——沒有父節點的節點——同時要顯示這個節點所有的子節點。對于這些子節點，函數也要獲取并顯示這個子節點的子節點。然后，對于他們的子節點，函數還要再顯示所有的子節點，然后依次類推。

也許你已經注意到了，這種函數的描述，有一種普遍的模式。我們可以簡單地只寫一個函數，用來獲得特定節點的子節點。這個函數然后要對每個子節點調用自身來再次顯示他們的子節點。這就是“遞歸”機制，因此稱這種方法叫“遞歸方法”。

<?php
// $parent 是我們要查看的子節點的父節點
// $level 會隨著我們深入樹的結構而不斷增加，
//        用來顯示一個清晰的縮進格式
function display_children($parent, $level) {
// 獲取$parent的全部子節點
$result = mysql_query('SELECT title FROM tree '.
'WHERE parent="'.$parent.'";');
// 顯示每個節點
while ($row = mysql_fetch_array($result)) {
// 縮進并顯示他的子節點的標題
echo str_repeat('  ',$level).$row['title']."\n";
// 再次調用這個函數來顯著這個子節點的子節點
display_children($row['title'], $level+1);
}
}
?>

要實現整個樹，我們只要調用函數時用一個空字符串作為$parent 和$level = 0: display_children('',0); 函數返回了我們的食品店的樹狀圖如下：

Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork

注意如果你只想看一個子樹，你可以告訴函數從另一個節點開始。例如，要顯示“Fruit”子樹，你只要display_children('Fruit',0);

<?php
// $node 是我們要查找路徑的那個節點的名字
function get_path($node) {
// 查找這個節點的父節點
$result = mysql_query('SELECT parent FROM tree '.
'WHERE title="'.$node.'";');
$row = mysql_fetch_array($result);
// 在這個array [5] 中保存數組
$path = array();
// 如果 $node 不是根節點，那么繼續
if ($row[’parent’]!=”) {
//  $node 的路徑的最后一部分是$node父節點的名稱
$path[] = $row[’parent’];
// 我們要添加這個節點的父節點的路徑到現在這個路徑
$path = array_merge(get_path($row[’parent’]), $path);
}
// 返回路徑
return $path;
}
?>

Array
(
[0] => Food
[1] => Fruit
[2] => Red
)

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

<?php
function display_tree($root) {
// 獲得$root節點的左邊和右邊的值
$result = mysql_query('SELECT lft, rgt FROM tree '.
'WHERE title="'.$root.'";');
$row = mysql_fetch_array($result);
// 以一個空的$right棧開始
$right = array();
// 現在，獲得$root節點的所有后序
$result = mysql_query('SELECT title, lft, rgt FROM tree '.
'WHERE lft BETWEEN '.$row['lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;');
// 顯示每一行
while ($row = mysql_fetch_array($result)) {
// 檢查棧里面有沒有元素
if (count($right)>0) {
// 檢查我們是否需要從棧中刪除一個節點
while ($right[count($right)-1]<$row['rgt']) {
array_pop($right);
}
}
// 顯示縮進的節點標題
echo str_repeat('  ',count($right)).$row['title']."\n";
// 把這個節點添加到棧中
$right[] = $row['rgt'];
}
}
?>

SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;

+-------+
| title |
+-------+
| Food  |
| Fruit |
| Red   |
+-------+

descendants = (right – left - 1) / 2

<?php
function rebuild_tree($parent, $left) {
// 這個節點的右值是左值加1
$right = $left+1;
// 獲得這個節點的所有子節點
$result = mysql_query('SELECT title FROM tree '.
'WHERE parent="'.$parent.'";');
while ($row = mysql_fetch_array($result)) {
// 對當前節點的每個子節點遞歸執行這個函數
// $right 是當前的右值，它會被rebuild_tree函數增加
$right = rebuild_tree($row['title'], $right);
}
// 我們得到了左值，同時現在我們已經處理這個節點我們知道右值的子節點
mysql_query('UPDATE tree SET lft='.$left.', rgt='.
$right.' WHERE title="'.$parent.'";');
// 返回該節點的右值+1
return $right+1;
}
?>

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;

INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';

Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork