求php+mysql 的二叉樹每一層的葉子統(tǒng)計

Hi，這是一個很有意思的問題，二叉樹，無限極分類一般都會用到遞歸。這里使用函數(shù)來模擬mysql查詢，解決思路如下：

創(chuàng)新互聯(lián)建站-云計算及IDC服務(wù)提供商，涵蓋公有云、IDC機房租用、成都多線服務(wù)器托管、等保安全、私有云建設(shè)等企業(yè)級互聯(lián)網(wǎng)基礎(chǔ)服務(wù)，服務(wù)電話：028-86922220

?php

header("Content-type:text/html;charset=utf-8");

$data?=?array(

array('id'=1,?'pid'=?0,?'name'=?'name1'),

array('id'=2,?'pid'=?1,?'name'=?'name2'),

array('id'=3,?'pid'=?2,?'name'=?'name3'),

array('id'=4,?'pid'=?3,?'name'=?'name4'),

array('id'=5,?'pid'=?2,?'name'=?'name5'),

array('id'=6,?'pid'=?2,?'name'=?'name6'),

array('id'=7,?'pid'=?2,?'name'=?'name7'),

array('id'=8,?'pid'=?7,?'name'=?'name8'),

array('id'=9,?'pid'=?8,?'name'=?'name9'),

array('id'=10,?'pid'=?9,?'name'=?'name10'),

array('id'=11,?'pid'=?10,?'name'=?'name11'),

array('id'=12,?'pid'=?11,?'name'=?'name12'),

array('id'=13,?'pid'=?12,?'name'=?'name13'),

array('id'=14,?'pid'=?13,?'name'=?'name14'),

array('id'=15,?'pid'=?14,?'name'=?'name15'),

array('id'=16,?'pid'=?1,?'name'=?'name16'),

array('id'=17,?'pid'=?16,?'name'=?'name17'),

array('id'=18,?'pid'=?17,?'name'=?'name18'),

array('id'=19,?'pid'=?18,?'name'=?'name19'),

array('id'=20,?'pid'=?3,?'name'=?'name20'),

array('id'=21,?'pid'=?3,?'name'=?'name21'),

array('id'=22,?'pid'=?2,?'name'=?'name22'),

);

$result?=?array();

$id?=?2;

$lv?=?20;

get_child_node_nums($id,?$lv,?$result);

foreach($result?as?$no?=?$row)

{

echo?'第'.($lv-$no+1).'層有'.count($row).'個葉子節(jié)點'.'br/';

}

p($result);

//模擬mysql根據(jù)pid獲取多行記錄

function?fetch_rows($pid=0)

{

global?$data;

$pid?=?(int)$pid;

$items?=?array();

//相當于sql語句:select?*?from?test?where?pid=$pid

echo?"select?*?from?test?where?pid=$pid;br/";

foreach($data?as?$row)

{

if($row['pid']?==?$pid)

{

$items[]?=?$row;

}

}

return?$items;

}

//$id為父節(jié)點id,?$lv為深度,?$result為引用傳值結(jié)果數(shù)組

function?get_child_node_nums($id,?$lv,?$result)

{

//首先根據(jù)其id作為子節(jié)點的pid獲取其所有子節(jié)點

$children?=?fetch_rows($id);

if($children)

{

//存儲其葉子節(jié)點

if(isset($result[$lv]))

{

$result[$lv]?=?array_merge($result[$lv],?$children);

}else{

$result[$lv]?=?$children;

}

$lv--;

if($lv??0)

{

foreach($children?as?$child)

{

$id?=?$child['id'];

get_child_node_nums($id,?$lv,?$result);

}

}

}

}

function?p($var)

{

echo?'pre';

if($var?===?false)

{

echo?'false';

}else?if($var?===?null){

print_r("null");

}else?if($var?===?''){

print_r("''");

}else{

print_r($var);

}

echo?'/pre';

}

輸出結(jié)果如下：

select?*?from?test?where?pid=2;

select?*?from?test?where?pid=3;

select?*?from?test?where?pid=4;

select?*?from?test?where?pid=20;

select?*?from?test?where?pid=21;

select?*?from?test?where?pid=5;

select?*?from?test?where?pid=6;

select?*?from?test?where?pid=7;

select?*?from?test?where?pid=8;

select?*?from?test?where?pid=9;

select?*?from?test?where?pid=10;

select?*?from?test?where?pid=11;

select?*?from?test?where?pid=12;

select?*?from?test?where?pid=13;

select?*?from?test?where?pid=14;

select?*?from?test?where?pid=15;

select?*?from?test?where?pid=22;

第1層有5個葉子節(jié)點

第2層有4個葉子節(jié)點

第3層有1個葉子節(jié)點

第4層有1個葉子節(jié)點

第5層有1個葉子節(jié)點

第6層有1個葉子節(jié)點

第7層有1個葉子節(jié)點

第8層有1個葉子節(jié)點

第9層有1個葉子節(jié)點

Array

(

[20]?=?Array

(

[0]?=?Array

(

[id]?=?3

[pid]?=?2

[name]?=?name3

)

[1]?=?Array

(

[id]?=?5

[pid]?=?2

[name]?=?name5

)

[2]?=?Array

(

[id]?=?6

[pid]?=?2

[name]?=?name6

)

[3]?=?Array

(

[id]?=?7

[pid]?=?2

[name]?=?name7

)

[4]?=?Array

(

[id]?=?22

[pid]?=?2

[name]?=?name22

)

)

[19]?=?Array

(

[0]?=?Array

(

[id]?=?4

[pid]?=?3

[name]?=?name4

)

[1]?=?Array

(

[id]?=?20

[pid]?=?3

[name]?=?name20

)

[2]?=?Array

(

[id]?=?21

[pid]?=?3

[name]?=?name21

)

[3]?=?Array

(

[id]?=?8

[pid]?=?7

[name]?=?name8

)

)

[18]?=?Array

(

[0]?=?Array

(

[id]?=?9

[pid]?=?8

[name]?=?name9

)

)

[17]?=?Array

(

[0]?=?Array

(

[id]?=?10

[pid]?=?9

[name]?=?name10

)

)

[16]?=?Array

(

[0]?=?Array

(

[id]?=?11

[pid]?=?10

[name]?=?name11

)

)

[15]?=?Array

(

[0]?=?Array

(

[id]?=?12

[pid]?=?11

[name]?=?name12

)

)

[14]?=?Array

(

[0]?=?Array

(

[id]?=?13

[pid]?=?12

[name]?=?name13

)

)

[13]?=?Array

(

[0]?=?Array

(

[id]?=?14

[pid]?=?13

[name]?=?name14

)

)

[12]?=?Array

(

[0]?=?Array

(

[id]?=?15

[pid]?=?14

[name]?=?name15

)

)

)

親測，望采納^_^。

MYSQL使用基礎(chǔ)、進階分享

MySQL是一個關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，由瑞典MySQL AB公司開發(fā)，屬于Oracle旗下產(chǎn)品，是最流行的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)之一。

端口是3306。

表很多時，使用linux腳本，需要根據(jù)需要修改一下：

和創(chuàng)建一樣，可以加上 if exists

可兩篇文章：

如：

用于在已有的表中添加、刪除或修改列。

添加 ADD

或

默認是添加到最后，但可以指定位置。 FIRST ：添加最前

AFTER 字段名 ：添加指定字段之后

例子：

刪除 DROP

修改 MODIFY 主要修改原列的類型或約束條件 同樣可以用 FIRST 和 AFTER 字段名 ，代表的是修改到哪里。

修改字段名 CHANGE

可以把表2的數(shù)據(jù)復(fù)制到表1中，但 不能復(fù)制約束性條件 。

單行

多行，注意 只有一個VALUES ：

不寫 (行1, 行2...) 這一部分的話，默認一一對應(yīng)

除了以上方法外，還可以用SET為每一行附上相應(yīng)的值。

假如沒有篩選的話，就給全部都修改了。可以用 WHERE 篩選。

假如 沒有篩選的話，就給全部刪除了 。相當于清空。

清空

先把表刪除，然后再建一個。與 DELETE FROM 相比， TRUNCATE 的效率更快，因為 DELETE FROM 是把記錄逐條刪除的。

查詢執(zhí)行的順序

FROM -- WHERE -- SELECT -- GROUP BY -- HAVING -- ORDER BY -- LIMIT

注意

當數(shù)據(jù)很大，上百萬的時候，使用LIMIT ... OFFSET ..的方式進行分頁十分浪費資源且耗時長。最好是結(jié)合WHERE使用，如：

REGEXP 使用正則表達進行匹配。 查詢時，需要搭配WHERE或HAVING使用 。

兩個表之間有交集且要用到兩個表的數(shù)據(jù)時，可以使用內(nèi)連接查詢。

LEFT JOIN 關(guān)鍵字從左表（table1）返回所有的行，即使右表（table2）中沒有匹配。如果右表中沒有匹配，則結(jié)果為 NULL。

用法：

RIGHT JOIN 關(guān)鍵字從右表（table2）返回所有的行，即使左表（table1）中沒有匹配。如果左表中沒有匹配，則結(jié)果為 NULL。 把LEFT JOIN的表1、表2調(diào)換順序，就是REGHT JOIN 。

FULL OUTER JOIN 關(guān)鍵字只要左表（table1）和右表（table2）其中一個表中存在匹配，則返回行. 相當于結(jié)合了 LEFT JOIN 和 RIGHT JOIN 的結(jié)果。

但 MySQL中不支持 FULL OUTER JOIN 。

即SELECT嵌套。

IN 一個查詢結(jié)果作為另一個查詢的條件。 如：

EXISTS 用于判斷查詢子句是否有記錄，如果有一條或多條記錄存在返回 True，否則返回 False。True時執(zhí)行。 如：

索引的本質(zhì)是一種排好序的數(shù)據(jù)結(jié)構(gòu)。利用索引可以提高查詢速度。

常見的索引有：

MySQL通過外鍵約束來保證表與表之間的數(shù)據(jù)的完整性和準確性。 外鍵的使用條件：

外鍵的好處：可以使得兩張表關(guān)聯(lián)，保證數(shù)據(jù)的一致性和實現(xiàn)一些級聯(lián)操作。

對已有的兩個表增加外鍵 比如：主表為A，子表為B，外鍵為aid，外鍵約束名字為a_fk_b

為子表添加一個字段，當做外鍵

為子表添加外鍵約束條件

假如刪除記錄報錯： [Err] 1451 -Cannot deleteorupdatea parent row: aforeignkeyconstraintfails (...)

這是因為MySQL中設(shè)置了foreign key關(guān)聯(lián)，造成無法更新或刪除數(shù)據(jù)。可以通過設(shè)置 FOREIGN_KEY_CHECKS 變量來避免這種情況。 第一步：禁用外鍵約束，我們可以使用： SETFOREIGN_KEY_CHECKS=0; 第二步：刪除數(shù)據(jù) 第三步：啟動外鍵約束，我們可以使用： SETFOREIGN_KEY_CHECKS=1; 查看當前FOREIGN_KEY_CHECKS的值，可用如下命令： SELECT @@FOREIGN_KEY_CHECKS;

使用 UNION 來組合兩個查詢，如果第一個查詢返回 M 行，第二個查詢返回 N 行，那么組合查詢的結(jié)果一般為 M+N 行。

每個查詢必須包含相同的列、表達式和聚集函數(shù)。

默認會去除相同行，如果需要 保留 相同行，使用 UNION ALL 。

只能包含一個 ORDER BY 子句，并且必須位于語句的最后 。

內(nèi)置函數(shù)很多, 見: MySQL 函數(shù)

我們一般使用 START TRANSACTION 或 BEGIN 開啟事務(wù), COMMIT 提交事務(wù)中的命令, SAVEPOINT : 相當于設(shè)置一個還原點, ROLLBACK TO : 回滾到某個還原點下

一般的使用格式如下:

開啟事務(wù)時, 默認加鎖

根據(jù)類型可分為共享鎖（SHARED LOCK）和排他鎖（EXCLUSIVE LOCK）或者叫讀鎖（READ LOCK）和寫鎖（WRITE LOCK）。

根據(jù)粒度劃分又分表鎖和行鎖。表鎖由數(shù)據(jù)庫服務(wù)器實現(xiàn)，行鎖由存儲引擎實現(xiàn)。

除此之外,我們可以顯示加鎖

加鎖時, 如果沒有索引，會鎖表，如果加了索引，就會鎖行

InnoDB默認支持行鎖，獲取鎖是分步的，并不是一次性獲取所有的鎖，因此在鎖競爭的時候就會出現(xiàn)死鎖的情況

解決方法:

即ACID特性:

由于并發(fā)事務(wù)會引發(fā)上面這些問題, 我們可以設(shè)置事務(wù)的隔離級別解決上面的問題.

MySQL的默認隔離級別（可重復(fù)讀）

查看當前會話隔離級別

方式1

方式2

設(shè)置隔離級別

主從集群的示意圖如下:

主要涉及三個線程： binlog 線程、 I/O 線程和 SQL 線程。

同步流程:

由于MySQL主從集群只會從主節(jié)點同步到從節(jié)點, 不會反過來同步, 所以需要讀寫分離

讀寫分離需要在業(yè)務(wù)層面實現(xiàn) , 寫數(shù)據(jù)只能在主節(jié)點上完成, 而讀數(shù)據(jù)可以在主節(jié)點或從節(jié)點上完成

索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)

MySQL的索引有

推薦兩個在線工具:

簡單來說, B樹是在紅黑樹(一個平衡二叉樹)的基礎(chǔ)上將一個節(jié)點存放多個值, 實現(xiàn)的, 降低了樹的高度, 每個節(jié)點都存放索引及對應(yīng)數(shù)據(jù)指針, 同一層的節(jié)點是遞增的

而B+樹在B樹的基礎(chǔ)上進行優(yōu)化, 非葉子節(jié)點存放 子節(jié)點的開始的索引, 葉子節(jié)點存放索引和數(shù)據(jù)的指針, 且葉子節(jié)點之間有雙向的指針

如下示意圖:

不同的引擎, 主鍵索引存放的數(shù)據(jù)也不一樣, 比如常見的 MyISAM 和 InnoDB

MyISAM 的B+樹葉子節(jié)點存放表數(shù)據(jù)的指針, InnoDB 的B+樹葉子節(jié)點存放處主鍵外的數(shù)據(jù)

其他的:

即多個列組成一個索引, 語法:

由于聯(lián)合索引的B+樹的結(jié)構(gòu), 根據(jù)列建立, 所以我們的查找條件也要根據(jù)索引列的順序( where column1=x, column2=y,columnN... ), 否則會全表掃描

如果你對列進行了 （+，-，*，/，!） , 那么都將不會走索引。

OR 引起的索引失效

OR 導(dǎo)致索引是在特定情況下的，并不是所有的 OR 都是使索引失效，如果OR連接的是 同 一個字段，那么索引 不會失效 ， 反之索引失效 。

這個我相信大家都明白，模糊搜索如果你前綴也進行模糊搜索，那么不會走索引。

這兩種用法，也將使索引失效。另 IN 會走索引，但是當IN的取值范圍較大時會導(dǎo)致索引失效，走全表掃描, 見: MySQL中使用IN會不會走索引

不走索引。

走索引。

所以設(shè)計表的時候, 建議不可為空, 而是將默認值設(shè)置為 "" ( NOT NULL DEFAULT "" )

mysql如何創(chuàng)建二叉樹

在二叉樹中有一種平衡二叉樹，通過平衡算法可以讓二叉樹兩邊的節(jié)點平均分布，這樣就能讓所有的索引查找都在一個近似的時間內(nèi)完成。而MySQL這類數(shù)據(jù)庫采用了二叉樹的升級版B+Tree的形式，每個節(jié)點有三個支葉，不過其算法原理仍然是平衡樹的原理。

MySQL BTREE索引

個人能力有限，如有錯誤請指出，共同學習。

二叉樹

B樹

B+樹

特點：

聚簇索引

二級索引

key數(shù)據(jù)存儲量估算：

若每個頁可以存1000個key，而且樹的高度是4，那么

前提條件如下：

插入步驟

步驟一

因為索引中還沒有數(shù)據(jù)，所以此時的B+樹只有一個空的根結(jié)點，又由于一個頁只能存3個key，首先將10，20，5插入進去（實際上此步發(fā)生了3次插入），然后在頁面內(nèi)做數(shù)據(jù)排序，最終結(jié)果如下圖：

步驟二：

由于根頁面已經(jīng)寫滿，此時插入8，將發(fā)生分裂（根頁面分裂），大致步驟如下：

注意：在分裂過程中，根結(jié)點始終是不會變的，不管變成多大的樹，根結(jié)點的頁面號始終如一。

步驟五：

插入數(shù)據(jù)40，發(fā)現(xiàn)比根結(jié)點23大，找到103號頁面，發(fā)現(xiàn)已滿，執(zhí)行分裂，分裂同上面葉子結(jié)點的分裂步驟。分裂后如圖所示：

步驟六：

繼續(xù)插入下一個數(shù)據(jù)9，因為比20小，找到101號頁面，發(fā)現(xiàn)已滿，需要做葉子結(jié)點分裂，如下圖：

傳統(tǒng)B+樹的數(shù)據(jù)刪除，一般都會有一個所謂的填充因子，來控制頁面數(shù)據(jù)的刪除比例，如果數(shù)據(jù)量小于這個填充因子所表示的數(shù)據(jù)量，就會有節(jié)點合并，這與分裂是相對應(yīng)的。

InnoDB的實現(xiàn)與傳統(tǒng)B+樹算法有不同之處，InnoDB在刪除索引數(shù)據(jù)時，會先檢查當前頁剩余的記錄數(shù)，如果只剩下一條記錄，就會直接將這個頁面從B+樹中摘除，也只有這種情況，InnoDB才會回收一個頁面，InnoDB的頁面沒有合并一說，但是對于根節(jié)點，即使索引數(shù)據(jù)全部刪除，根節(jié)點頁依然存在，只不過是以空頁的形式存在。

下面舉個例子描述索引刪除過程，前提條件與前面插入記錄時一致。

刪除數(shù)據(jù) 50

刪除過程全部結(jié)束，最終得到一個空的索引頁。

《MySQL運維內(nèi)參》

B+樹動畫演示：

文章標題：mysql怎么做二叉樹 實現(xiàn)一個二叉樹
網(wǎng)址分享：http://vcdvsql.cn/article32/hhhppc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、建站公司、用戶體驗、靜態(tài)網(wǎng)站、網(wǎng)站內(nèi)鏈、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)