mysql怎么做二叉树 实现一个二叉树
求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://mswzjz.cn/article/hhhppc.html