亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

在數(shù)據(jù)庫中存儲層級結(jié)構(gòu)

系統(tǒng) 2029 0

在數(shù)據(jù)庫中存儲層級結(jié)構(gòu) - 殘陽似血的博客

在數(shù)據(jù)庫中存儲層級結(jié)構(gòu)

位于分類 技巧集錦

本文參考自 這篇文章 。文章是2003年的，但是現(xiàn)在來看仍然有著實(shí)際意義。

層級結(jié)構(gòu)，也叫樹形結(jié)構(gòu)。在實(shí)際應(yīng)用中，你經(jīng)常需要保存層級結(jié)構(gòu)到數(shù)據(jù)庫中。比如說：你的網(wǎng)站上的目錄。不過，除非使用類XML的數(shù)據(jù)庫，通用的關(guān)系數(shù)據(jù)庫很難做到這點(diǎn)。

對于樹形數(shù)據(jù)的存儲有很多種方案。主要的方法有兩種：鄰接表模型，以及修改過的前序遍歷算法。本文將會討論這兩種方法的實(shí)現(xiàn)。這里的例子沿用參考文章中的例子，原文使用的PHP，這里將會用Java替代。（本例使用Mysql數(shù)據(jù)庫，Java如何連接Mysql，見備注一。）文中使用虛擬的在線食品商店作例子。這個食品商店通過類別、顏色以及種類來來組織它的食品。如圖所示：

1）首先是鄰接表模型。

鄰接表相當(dāng)簡單。只需要寫一個遞歸函數(shù)來遍歷這個樹。我們的食品商店的例子用鄰接表模型存儲時看起來就像是這樣：

通過鄰接表模型存儲法中，我們可以看到Pear，它的父節(jié)點(diǎn)是Green，而Green的父節(jié)點(diǎn)又是Fruit，以此類推。而根節(jié)點(diǎn)是沒有父節(jié)點(diǎn)的。這里為了方便觀看，parent字段使用的字符串，實(shí)際應(yīng)用中只要使用每個節(jié)點(diǎn)的ID即可。

現(xiàn)在已經(jīng)在數(shù)據(jù)庫中插入完畢數(shù)據(jù)，接下來開始先顯示這棵樹。

打印這棵樹：

這里我們只需要寫一個簡單的遞歸函數(shù)就可以實(shí)現(xiàn)。打印某節(jié)點(diǎn)時，如果該節(jié)點(diǎn)有子節(jié)點(diǎn)就打印其子節(jié)點(diǎn)。源代碼如下：

1
2
3
4
5
6
7
8
9
10
11
12
public static void displayTree( int parentId, int level)
???? throws SQLException {
???? setUp();
???? ResultSet result = dbc.query(
???????? "SELECT ID, title FROM `adjacency_list` WHERE parentid="
???????? + parentId);
???? while (result.next()){
???????? System.out.println(repeatStr( "? " , level)
???????????? + result.getString( "title" ));
???????? displayTree(result.getInt( "ID" ), level+ 1 );
???? }
}

要打印整棵樹，我們只要運(yùn)行代碼：

1
displayTree( 0 , 0 );

這個函數(shù)打印出以下結(jié)果： 

                Food
      Fruit
        Green
          Pear
        Red
          Cherry
        Yellow
          Banana
      Meat
        Beef
        Pork

求節(jié)點(diǎn)的路徑

有時候我們需要知道某個節(jié)點(diǎn)所在的路徑。舉例來說，“Cherry”所在的路徑為Food > Fruit > Red > Cherry。在這里，我們可以從Cherry開始查起，然后遞歸查詢查詢節(jié)點(diǎn)前的節(jié)點(diǎn)，直到某節(jié)點(diǎn)的父節(jié)點(diǎn)ID為0。源代碼如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static List<String> getPath( int id)
???? throws SQLException{
???? List<String> paths = new ArrayList<String>();
???? setUp();
???? ResultSet result = dbc.query(
???????? "SELECT parentid, title FROM `adjacency_list` WHERE ID="
???????? + id);
???? result.next();
???? int parentid = result.getInt( "parentid" );
???? if (parentid != 0 ){
???????? paths.addAll(getPath(parentid));
???? }
???? paths.add(result.getString( "title" ));
???? return paths;
}

我們用以下代碼來打印結(jié)果：

1
2
3
4
5
6
List<String> paths = getPath( 6 );
int i = 0 ;
for (String path: paths){
???? System.out.println( "[" + String.valueOf(i) + "] ==> " + path);
???? i++;
}

得到以下結(jié)果： 

                [0] ==> Food
    [1] ==> Fruit
    [2] ==> Red
    [3] ==> Cherry

缺點(diǎn)

我們可以看到，用鄰接表模型確實(shí)是個不錯的方法。它簡單易懂，而且實(shí)現(xiàn)的代碼寫起來也很容易。那么，缺點(diǎn)是什么呢？那就是，鄰接表模型執(zhí)行起來效率低下。我們對于每個結(jié)果，期望只需要一次查詢；可是當(dāng)使用鄰接表模型時嵌套的遞歸使用了多次查詢，當(dāng)樹很大的時候，這種慢就會表現(xiàn)得尤為明顯。另外，對于一門程序語言來說，除了Lisp這種，大多數(shù)不是為了遞歸而設(shè)計。當(dāng)一個節(jié)點(diǎn)深度為4時，它得同時生成4個函數(shù)實(shí)例，它們都需要花費(fèi)時間、占用一定的內(nèi)存空間。所以，鄰接表模型效率的低下可想而知。

就像在程序世界經(jīng)常遇到的一樣。上帝是公平的，當(dāng)在執(zhí)行時效率低下，意味著可以增加預(yù)處理的程度。那么就讓我們來看另外一種存儲樹形結(jié)構(gòu)的方法。如之前所講，我們希望能夠減少查詢的數(shù)量，最好是只做到查詢一次數(shù)據(jù)庫。

先來講解一下原理。現(xiàn)在我們把樹“橫”著放。如下圖所示，我們首先從根節(jié)點(diǎn)（“Food”）開始，先在它左側(cè)標(biāo)記“1”，然后我們到“Fruit”，左側(cè)標(biāo)記“2”，接著按照前序遍歷的順序遍歷完樹，依次在每個節(jié)點(diǎn)的左右側(cè)標(biāo)記數(shù)字。

相信你也在圖中發(fā)現(xiàn)一些規(guī)律，沒錯。比如，“Red”節(jié)點(diǎn)左邊的數(shù)為3、右邊的數(shù)為6，它是Food（1-18）的后代。同樣的，我們可以注意到，左數(shù)大于2、右數(shù)小于11的節(jié)點(diǎn)都是“Fruit”的子孫。現(xiàn)在，所有的節(jié)點(diǎn)將以左數(shù)-右數(shù)的方式存儲，這種通過遍歷一個樹、然后給每一個節(jié)點(diǎn)標(biāo)注左數(shù)、右數(shù)的方式稱為修改過的前序遍歷算法。

2）修改過的前序遍歷算法

在看完了介紹之后，我們要來討論具體的實(shí)現(xiàn)。在這之前，先來看一下，數(shù)據(jù)庫中表存儲這些數(shù)的情況。

在這種存儲方式中，我們實(shí)際上是不需要parent這個字段的。

打印樹：

如之前的介紹。如果要想打印樹，你只需要知道你要檢索的節(jié)點(diǎn)。比如，想要打印“Fruit”的子樹，可以查詢左數(shù)大于2而小于11的節(jié)點(diǎn)。SQL語句就像這樣：

1
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

返回結(jié)果如下：

有時候，如果進(jìn)行過增、刪的操作，表中的數(shù)據(jù)可能就不是正確的順序。沒問題，只要使用“ORDER BY”語句就可以了，就像這樣：

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

現(xiàn)在唯一的問題是縮進(jìn)問題。

正如我們面對樹的問題常常會想到的方案——棧。這里，我們可以維護(hù)一個只保存右數(shù)的棧。當(dāng)當(dāng)前節(jié)點(diǎn)的右數(shù)值大于棧頂元素的值（說明棧頂元素的子樹都以遍歷完畢），這個時候彈出棧頂值。再循環(huán)檢查棧頂值，直到棧頂值小于當(dāng)前查詢節(jié)點(diǎn)的右數(shù)值。這個時候只要檢查棧中元素，有多少個元素說明當(dāng)前查詢節(jié)點(diǎn)有多少個祖先節(jié)點(diǎn)（設(shè)為n）。只需要打印n個空格即可。代碼如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static void displayTree(String root) throws SQLException{
???? setUp();
???? ResultSet result = dbc.query( "SELECT lft, rgt "
???????? + "FROM `modified_preorder_travesal` WHERE title='"
???????? + root + "';" );
???? result.next();
???????? ?
???? Stack<Integer> right = new Stack<Integer>();
???????? ?
???? result = dbc.query( "SELECT title, lft, rgt "
???????? + "FROM `modified_preorder_travesal`"
???????? + " WHERE lft BETWEEN "
???????? + String.valueOf(result.getInt( "lft" ))
???????? + " AND "
???????? + String.valueOf(result.getInt( "rgt" ))
???????? + " ORDER BY lft ASC;" );
???????? ?
???? while (result.next()){
???????? if (right.size() > 0 ){
???????????? Integer current = right.peek();
???????????? while (current < result.getInt( "rgt" )){
???????????????? right.pop();
???????????????? current = right.peek();
???????????? }
???????? }
???????????? ?
???????? System.out.println(repeatStr( "? " , right.size())
???????????? + result.getString( "title" ));
???????????? ?
???????? right.push(result.getInt( "rgt" ));
???? }
}

運(yùn)行代碼，打印結(jié)果和之前鄰接表模型打印的結(jié)果一樣。但是新方法更快，原因就是：沒有遞歸，且一共只使用兩次查詢。

求節(jié)點(diǎn)的路徑：

在修改過的前序遍歷算法的實(shí)現(xiàn)中，我們同樣需要求節(jié)點(diǎn)的路徑。不過這不是很困難，對于某節(jié)點(diǎn)，我們只需求出左數(shù)值小于其左數(shù)值、右數(shù)大于其右數(shù)的所有節(jié)點(diǎn)。比如說“Cherry”這個節(jié)點(diǎn)（4-5），我們可以這么寫SQL查詢：

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

這里同樣別忘了添加“ORDER BY”語句。執(zhí)行以后返回結(jié)果：

求有多少子孫：

已知某節(jié)點(diǎn)的左數(shù)和右數(shù)，它的子孫的求法也就相當(dāng)簡單了，用如下方法：

descendants?=?(right - left?-?1)?/?2?

自動生成表：

這兒的自動生成表指的是：如何把一個表從鄰接表模型轉(zhuǎn)換成修改過的前序遍歷模型。我們在開始的臨界表上增加"lft“和”rgt“字段。執(zhí)行以下代碼，完成轉(zhuǎn)換：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int rebuildTree( int parentId, int left) throws SQLException {
???? setUp();
???????? ?
???? int right = left + 1 ;
???????? ?
???? ResultSet result = dbc.query( "SELECT ID, title FROM `adjacency_list` WHERE "
???????? + "parentid=" + parentId);
???????? ?
???? while (result.next()){
???????? right = rebuildTree(result.getInt( "ID" ), right);
???? }
???????? ?
???? dbc.update( "UPDATE `adjacency_list` SET lft=" + String.valueOf(left)
???????? + ", rgt=" + String.valueOf(right)
???????? + " WHERE ID='" + parentId + "';" );
???????? ?
???? return right + 1 ;
}

開始執(zhí)行只要運(yùn)行以下代碼：

1
rebuildTree( 1 , 1 );

我們所寫的運(yùn)行函數(shù)是一個遞歸函數(shù)。對于某一節(jié)點(diǎn)，如果其沒有子孫節(jié)點(diǎn)，那么他的右數(shù)值等于左數(shù)值+1；如果有那么返回其子樹右數(shù)值+1。這個函數(shù)稍微有點(diǎn)復(fù)雜，不過梳理通了以后就不難理解。

這個函數(shù)將會從根節(jié)點(diǎn)開始遍歷整個樹。運(yùn)行了可以發(fā)現(xiàn)和我們之前手動所建的表一樣。這里有個快速檢查的方法：那就是檢查根節(jié)點(diǎn)的右數(shù)值，如果它等于節(jié)點(diǎn)總數(shù)的2倍，那就是正確的。

增加節(jié)點(diǎn)：

增加節(jié)點(diǎn)有兩種方法：1）保留parentid字段，當(dāng)增加節(jié)點(diǎn)后，運(yùn)行一遍“rebuildTree”方法。這么做看起來很簡單，不過你應(yīng)該知道，這么做效率低下，尤其是大樹時。那么第二種方法呢？2）首先我們得為添加的節(jié)點(diǎn)騰出空間。比如，我們想添加“Strawberry“到”Red“節(jié)點(diǎn)下，那么“Red”節(jié)點(diǎn)的右數(shù)就得從6到8，而“Yellow”就得從7-10變成9-12，以此類推。更新Red節(jié)點(diǎn)就意味著大于5的左數(shù)和右數(shù)都要增加2。

我們先運(yùn)行以下SQL語句：

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

現(xiàn)在我們可以添加“Strawberry”到“Red”下，其左數(shù)為6、右數(shù)為7。

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

再次運(yùn)行“displayTree”方法，會發(fā)現(xiàn)“Strawberry”已被添加其中。刪除節(jié)點(diǎn)有著差不多的步驟，這里就略去不提了。各位感興趣的話可以自己實(shí)現(xiàn)。

缺點(diǎn)：

首先，修改過的前序遍歷算法似乎更難理解。但是它有著鄰接表模型無法比擬的速度優(yōu)勢，雖然，在增或著刪數(shù)據(jù)的時候步驟多了些，但是，查詢的時候只需要一條SQL語句。不過，這里我要提醒，當(dāng)使用前序遍歷算法存儲樹的時候，要注意臨界區(qū)問題，就是在增或者刪的時候，不要出現(xiàn)其他的數(shù)據(jù)庫操作。

關(guān)于在數(shù)據(jù)庫中存儲層級數(shù)據(jù)的內(nèi)容就講到這里。如果你使用的Python語言的Django框架，應(yīng)該覺得慶幸。因?yàn)橐呀?jīng)有開源插件幫你實(shí)現(xiàn)了。項(xiàng)目名字叫MPTT，主頁在 這里 。以后，我會對MPTT的用法以及源碼實(shí)現(xiàn)作詳細(xì)說明。在此之前，如果能力夠，參考 官方文檔 就可以了。

備注一：

各種數(shù)據(jù)庫的JDBC驅(qū)動連接方式及下載，見 這里 。Mysql下載的 快速鏈接 。

下載完解壓縮，把其中的mysql-connector-java-***-bin.jar（***為版本）文件拷貝至"yourjdkpath"/jre/lib/ext，我的路徑為：/usr/lib/jvm/java-6-openjdk/jre/lib/ext/。

這個文件夾是只讀的，修改權(quán)限用chmod命令。

連接數(shù)據(jù)庫的參考代碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.io.*;
import java.sql.*;
import java.util.*;
?
public class DBConnection {
???? private String driver = null ;
???? private String url = null ;
???? private String username = null ;
???? private String password = null ;
???? private Connection con = null ;
???? ?
???? public DBConnection(){
???????? this .driver = "org.gjt.mm.mysql.Driver" ;
???????? this .url = "jdbc: mysql://localhost:3306/Tree " ;
???????? this .username = "root" ;
???????? this .password = "" ;
???? }
???? ?
???? public DBConnection(String driver, String url, String username, String password){
???????? this .driver = driver;
???????? this .url = url;
???????? this .username = username;
???????? this .password = password;
???? }
???? ?
???? public Connection makeConnection(){
???????? con = null ;
???????? try {
???????????? Class.forName(driver);
???????????? con = DriverManager.getConnection(url, username, password);
???????????? System.out.println( "連接Mysql成功" );
???????? }
???????? catch (SQLException sqle){
???????????? sqle.printStackTrace();
???????? }
???????? catch (ClassNotFoundException ex){
???????????? ex.printStackTrace();
???????? }
???????? return con;
???? }
???? ?
???? public void closeConnection(){
???????? try {
???????????? con.close();
???????? }
???????? catch (SQLException sqle){
???????????? sqle.printStackTrace();
???????????? ?
???????? }
???? }
???? ?
???? public static void main(String[] args){
???????? DBConnection dbc = new DBConnection();
???????? dbc.makeConnection();
???????? dbc.closeConnection();
???? }
}

四月 16

文章信息

標(biāo)簽

4條留言

  1. 樹的增刪改查會導(dǎo)致整個編碼都更新吧.

  2. 所以很難在項(xiàng)目中應(yīng)用.

    • 兩種方法都在項(xiàng)目中使用過，由于都是小項(xiàng)目，所以對比效果不明顯。比較折中的辦法，是保存所有父節(jié)點(diǎn)id來組成TreeCode，當(dāng)然，這樣的話也只能應(yīng)付小項(xiàng)目

在數(shù)據(jù)庫中存儲層級結(jié)構(gòu)


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索：z360901061

微信掃一掃加我為好友

QQ號聯(lián)系： 360901061

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。

【本文對您有幫助就好】元

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧，站長會非常 感謝您的哦！！！

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板： 欧美一级第一免费高清 | 欧美日韩一区二区高清视 | 久久婷婷一区二区三区 | 亚洲国产精品二区久久 | 久久中文字幕一区二区三区 | 国产精品视频一区牛牛视频 | 性欧美精品久久久久久久 | 香蕉久久一区二区三区 | 天天碰免费视频 | 欧美日韩99 | 九九精品久久久久久噜噜 | 欧美日韩激情在线一区 | 免费两性的视频网站 | 欧美午夜视频 | 国产理论最新国产精品视频 | 亚洲国产精品久久久天堂麻豆 | 成人性色生活片免费网 | 成熟热自由日本语亚洲人 | 一a级毛片| 国内精品一区二区2021在线 | 国产成人午夜精品5599 | 亚洲性在线 | 国产精品全国探花泡良大师 | 欧美亚洲国产精品久久第一页 | 宅男噜噜噜66一区二区 | 日韩一区二区不卡 | 日本人一级大毛片 | 国产精品一区三区 | 麻豆国产精品免费视频 | 欧美午夜精品久久久久免费视 | 日韩天堂在线 | 亚洲伊人精品综合在合线 | 日日摸夜夜欧美一区二区 | 亚洲欧美日本另类 | 国产一级一片免费播放 | 尤物久久99热国产综合 | 久久九九热re6这里有精品 | 欧美成人精品免费播放 | 天天草天天干天天 | 婷婷涩涩| 草草在线观看视频 |