求php+mysql 的二叉树每一层的叶子统计

Hi，这是一个很有意思的问题，二叉树，无限极分类一般都会用到递归。这里使用函数来模拟mysql查询，解决思路如下：

创新互联建站-云计算及IDC服务提供商，涵盖公有云、IDC机房租用、成都多线服务器托管、等保安全、私有云建设等企业级互联网基础服务，服务电话：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).'个叶子节点'.'br/';

}

p($result);

//模拟mysql根据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为父节点id, $lv为深度, $result为引用传值结果数组

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

{

//首先根据其id作为子节点的pid获取其所有子节点

$children = fetch_rows($id);

if($children)

{

//存储其叶子节点

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';

}

输出结果如下：

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个叶子节点

第2层有4个叶子节点

第3层有1个叶子节点

第4层有1个叶子节点

第5层有1个叶子节点

第6层有1个叶子节点

第7层有1个叶子节点

第8层有1个叶子节点

第9层有1个叶子节点

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使用基础、进阶分享

MySQL是一个关系型数据库管理系统，由瑞典MySQL AB公司开发，属于Oracle旗下产品，是最流行的关系型数据库管理系统之一。

端口是3306。

表很多时，使用linux脚本，需要根据需要修改一下：

和创建一样，可以加上 if exists

可两篇文章：

如：

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

添加 ADD

或

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

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

例子：

删除 DROP

修改 MODIFY 主要修改原列的类型或约束条件 同样可以用 FIRST 和 AFTER 字段名 ，代表的是修改到哪里。

修改字段名 CHANGE

可以把表2的数据复制到表1中，但 不能复制约束性条件 。

单行

多行，注意 只有一个VALUES ：

不写 (行1, 行2...) 这一部分的话，默认一一对应

除了以上方法外，还可以用SET为每一行附上相应的值。

假如没有筛选的话，就给全部都修改了。可以用 WHERE 筛选。

假如 没有筛选的话，就给全部删除了 。相当于清空。

清空

先把表删除，然后再建一个。与 DELETE FROM 相比， TRUNCATE 的效率更快，因为 DELETE FROM 是把记录逐条删除的。

查询执行的顺序

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

注意

当数据很大，上百万的时候，使用LIMIT ... OFFSET ..的方式进行分页十分浪费资源且耗时长。最好是结合WHERE使用，如：

REGEXP 使用正则表达进行匹配。 查询时，需要搭配WHERE或HAVING使用 。

两个表之间有交集且要用到两个表的数据时，可以使用内连接查询。

LEFT JOIN 关键字从左表（table1）返回所有的行，即使右表（table2）中没有匹配。如果右表中没有匹配，则结果为 NULL。

用法：

RIGHT JOIN 关键字从右表（table2）返回所有的行，即使左表（table1）中没有匹配。如果左表中没有匹配，则结果为 NULL。 把LEFT JOIN的表1、表2调换顺序，就是REGHT JOIN 。

FULL OUTER JOIN 关键字只要左表（table1）和右表（table2）其中一个表中存在匹配，则返回行. 相当于结合了 LEFT JOIN 和 RIGHT JOIN 的结果。

但 MySQL中不支持 FULL OUTER JOIN 。

即SELECT嵌套。

IN 一个查询结果作为另一个查询的条件。 如：

EXISTS 用于判断查询子句是否有记录，如果有一条或多条记录存在返回 True，否则返回 False。True时执行。 如：

索引的本质是一种排好序的数据结构。利用索引可以提高查询速度。

常见的索引有：

MySQL通过外键约束来保证表与表之间的数据的完整性和准确性。 外键的使用条件：

外键的好处：可以使得两张表关联，保证数据的一致性和实现一些级联操作。

对已有的两个表增加外键 比如：主表为A，子表为B，外键为aid，外键约束名字为a_fk_b

为子表添加一个字段，当做外键

为子表添加外键约束条件

假如删除记录报错： [Err] 1451 -Cannot deleteorupdatea parent row: aforeignkeyconstraintfails (...)

这是因为MySQL中设置了foreign key关联，造成无法更新或删除数据。可以通过设置 FOREIGN_KEY_CHECKS 变量来避免这种情况。 第一步：禁用外键约束，我们可以使用： SETFOREIGN_KEY_CHECKS=0; 第二步：删除数据 第三步：启动外键约束，我们可以使用： SETFOREIGN_KEY_CHECKS=1; 查看当前FOREIGN_KEY_CHECKS的值，可用如下命令： SELECT @@FOREIGN_KEY_CHECKS;

使用 UNION 来组合两个查询，如果第一个查询返回 M 行，第二个查询返回 N 行，那么组合查询的结果一般为 M+N 行。

每个查询必须包含相同的列、表达式和聚集函数。

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

只能包含一个 ORDER BY 子句，并且必须位于语句的最后 。

内置函数很多, 见: MySQL 函数

我们一般使用 START TRANSACTION 或 BEGIN 开启事务, COMMIT 提交事务中的命令, SAVEPOINT : 相当于设置一个还原点, ROLLBACK TO : 回滚到某个还原点下

一般的使用格式如下:

开启事务时, 默认加锁

根据类型可分为共享锁（SHARED LOCK）和排他锁（EXCLUSIVE LOCK）或者叫读锁（READ LOCK）和写锁（WRITE LOCK）。

根据粒度划分又分表锁和行锁。表锁由数据库服务器实现，行锁由存储引擎实现。

除此之外,我们可以显示加锁

加锁时, 如果没有索引，会锁表，如果加了索引，就会锁行

InnoDB默认支持行锁，获取锁是分步的，并不是一次性获取所有的锁，因此在锁竞争的时候就会出现死锁的情况

解决方法:

即ACID特性:

由于并发事务会引发上面这些问题, 我们可以设置事务的隔离级别解决上面的问题.

MySQL的默认隔离级别（可重复读）

查看当前会话隔离级别

方式1

方式2

设置隔离级别

主从集群的示意图如下:

主要涉及三个线程： binlog 线程、 I/O 线程和 SQL 线程。

同步流程:

由于MySQL主从集群只会从主节点同步到从节点, 不会反过来同步, 所以需要读写分离

读写分离需要在业务层面实现 , 写数据只能在主节点上完成, 而读数据可以在主节点或从节点上完成

索引是帮助MySQL高效获取数据的排好序的数据结构

MySQL的索引有

推荐两个在线工具:

简单来说, B树是在红黑树(一个平衡二叉树)的基础上将一个节点存放多个值, 实现的, 降低了树的高度, 每个节点都存放索引及对应数据指针, 同一层的节点是递增的

而B+树在B树的基础上进行优化, 非叶子节点存放 子节点的开始的索引, 叶子节点存放索引和数据的指针, 且叶子节点之间有双向的指针

如下示意图:

不同的引擎, 主键索引存放的数据也不一样, 比如常见的 MyISAM 和 InnoDB

MyISAM 的B+树叶子节点存放表数据的指针, InnoDB 的B+树叶子节点存放处主键外的数据

其他的:

即多个列组成一个索引, 语法:

由于联合索引的B+树的结构, 根据列建立, 所以我们的查找条件也要根据索引列的顺序( where column1=x, column2=y,columnN... ), 否则会全表扫描

如果你对列进行了 （+，-，*，/，!） , 那么都将不会走索引。

OR 引起的索引失效

OR 导致索引是在特定情况下的，并不是所有的 OR 都是使索引失效，如果OR连接的是 同 一个字段，那么索引 不会失效 ， 反之索引失效 。

这个我相信大家都明白，模糊搜索如果你前缀也进行模糊搜索，那么不会走索引。

这两种用法，也将使索引失效。另 IN 会走索引，但是当IN的取值范围较大时会导致索引失效，走全表扫描, 见: MySQL中使用IN会不会走索引

不走索引。

走索引。

所以设计表的时候, 建议不可为空, 而是将默认值设置为 "" ( NOT NULL DEFAULT "" )

mysql如何创建二叉树

在二叉树中有一种平衡二叉树，通过平衡算法可以让二叉树两边的节点平均分布，这样就能让所有的索引查找都在一个近似的时间内完成。而MySQL这类数据库采用了二叉树的升级版B+Tree的形式，每个节点有三个支叶，不过其算法原理仍然是平衡树的原理。

MySQL BTREE索引

个人能力有限，如有错误请指出，共同学习。

二叉树

B树

B+树

特点：

聚簇索引

二级索引

key数据存储量估算：

若每个页可以存1000个key，而且树的高度是4，那么

前提条件如下：

插入步骤

步骤一

因为索引中还没有数据，所以此时的B+树只有一个空的根结点，又由于一个页只能存3个key，首先将10，20，5插入进去（实际上此步发生了3次插入），然后在页面内做数据排序，最终结果如下图：

步骤二：

由于根页面已经写满，此时插入8，将发生分裂（根页面分裂），大致步骤如下：

注意：在分裂过程中，根结点始终是不会变的，不管变成多大的树，根结点的页面号始终如一。

步骤五：

插入数据40，发现比根结点23大，找到103号页面，发现已满，执行分裂，分裂同上面叶子结点的分裂步骤。分裂后如图所示：

步骤六：

继续插入下一个数据9，因为比20小，找到101号页面，发现已满，需要做叶子结点分裂，如下图：

传统B+树的数据删除，一般都会有一个所谓的填充因子，来控制页面数据的删除比例，如果数据量小于这个填充因子所表示的数据量，就会有节点合并，这与分裂是相对应的。

InnoDB的实现与传统B+树算法有不同之处，InnoDB在删除索引数据时，会先检查当前页剩余的记录数，如果只剩下一条记录，就会直接将这个页面从B+树中摘除，也只有这种情况，InnoDB才会回收一个页面，InnoDB的页面没有合并一说，但是对于根节点，即使索引数据全部删除，根节点页依然存在，只不过是以空页的形式存在。

下面举个例子描述索引删除过程，前提条件与前面插入记录时一致。

删除数据 50

删除过程全部结束，最终得到一个空的索引页。

《MySQL运维内参》

B+树动画演示：

当前名称：mysql怎么做二叉树 实现一个二叉树
标题来源：http://azwzsj.com/article/hhhppc.html