数据库优化是系统工程，性能的提升靠整体。本课程将面面俱到的讲解提升数据库性能的各种因素，让你在最短的时间从小白到资深，将数据库整体架构了然于胸
第1章 实例和故事 试看7 节 | 50分钟
决定电商11大促成败的各个关键因素。
收起列表
视频：1-1 什么决定了电商双11大促的成败 (04:04)试看
视频：1-2 在双11大促中的数据库服务器 (06:03)
视频：1-3 在大促中什么影响了数据库性能 (07:55)
视频：1-4 大表带来的问题 (14:13)
视频：1-5 大事务带来的问题 (17:27)
作业：1-6 讨论题在日常工作中如何应对高并发大数据量对数据库性能挑战
作业：1-7 讨论题在MySQL中事务的作用是什么？
第2章 什么影响了MySQL性能 试看30 节 | 210分钟
详细介绍影响性能各个因素，包括硬件、 *** 作系统等等。
收起列表
视频：2-1 影响性能的几个方面 (04:08)试看
视频：2-2 CPU资源和可用内存大小 (10:54)
视频：2-3 磁盘的配置和选择 (04:44)
视频：2-4 使用RAID增加传统机器硬盘的性能 (11:30)
视频：2-5 使用固态存储SSD或PCIe卡 (08:35)
视频：2-6 使用网络存储SAN和NAS (07:16)
视频：2-7 总结：服务器硬件对性能的影响 (03:27)
视频：2-8 *** 作系统对性能的影响-MySQL适合的 *** 作系统 (03:50)
视频：2-9 CentOS系统参数优化 (11:43)
视频：2-10 文件系统对性能的影响 (03:29)
视频：2-11 MySQL体系结构 (05:29)
视频：2-12 MySQL常用存储引擎之MyISAM (13:23)
视频：2-13 MySQL常用存储引擎之Innodb (10:44)
视频：2-14 Innodb存储引擎的特性(1) (15:24)
视频：2-15 Innodb存储引擎的特性(2) (08:44)
视频：2-16 MySQL常用存储引擎之CSV (09:19)
视频：2-17 MySQL常用存储引擎之Archive (06:08)
视频：2-18 MySQL常用存储引擎之Memory (10:40)
视频：2-19 MySQL常用存储引擎之Federated (11:21)
视频：2-20 如何选择存储引擎 (04:33)
视频：2-21 MySQL服务器参数介绍 (08:04)
视频：2-22 内存配置相关参数 (09:24)
视频：2-23 IO相关配置参数 (10:01)
视频：2-24 安全相关配置参数 (06:13)
视频：2-25 其它常用配置参数 (03:41)
视频：2-26 数据库设计对性能的影响 (04:36)
视频：2-27 总结 (01:32)
作业：2-28 讨论题你会如何配置公司的数据库服务器硬件？
作业：2-29 讨论题你认为对数据库性能影响最大的因素是什么
作业：2-30 讨论题做为电商的DBA，建议开发选哪种MySQL存储引擎
第3章 MySQL基准测试8 节 | 65分钟
了解基准测试,MySQL基准测试工具介绍及实例演示。
收起列表
视频：3-1 什么是基准测试 (02:20)
视频：3-2 如何进行基准测试 (09:00)
视频：3-3 基准测试演示实例 (11:18)
视频：3-4 Mysql基准测试工具之mysqlslap (13:30)
视频：3-5 Mysql基准测试工具之sysbench (11:07)
视频：3-6 sysbench基准测试演示实例 (17:11)
作业：3-7 讨论题MySQL基准测试是否可以体现出业务系统的真实性能
作业：3-8 实 *** 题参数不同取值对性能的影响
第4章 MySQL数据库结构优化14 节 | 85分钟
详细介绍数据库结构设计、范式和反范式设计、物理设计等等。
收起列表
视频：4-1 数据库结构优化介绍 (06:52)
视频：4-2 数据库结构设计 (14:49)
视频：4-3 需求分析及逻辑设计 (11:00)
视频：4-4 需求分析及逻辑设计-反范式化设计 (06:44)
视频：4-5 范式化设计和反范式化设计优缺点 (04:06)
视频：4-6 物理设计介绍 (05:17)
视频：4-7 物理设计-数据类型的选择 (18:59)
视频：4-8 物理设计-如何存储日期类型 (13:37)
视频：4-9 物理设计-总结 (02:37)
图文：4-10 说明MyISAM和Innodb存储引擎的5点不同
作业：4-11 讨论题判断表结构是否符合第三范式要求如不满足要如何修改
作业：4-12 实 *** 题请设计一个电商订单系统的数据库结构
作业：4-13 讨论题以下那个字段适合作为Innodb表的主建使用
作业：4-14 讨论题请为下表中的字段选择合适的数据类型
第5章 MySQL高可用架构设计 试看24 节 | 249分钟
详细介绍二进制日志及其对复制的影响、GTID的复制、MMM、MHA等等。
收起列表
视频：5-1 mysql复制功能介绍 (04:58)
视频：5-2 mysql二进制日志 (22:05)
视频：5-3 mysql二进制日志格式对复制的影响 (09:37)
视频：5-4 mysql复制工作方式 (03:08)
视频：5-5 基于日志点的复制 (20:06)
视频：5-6 基于GTID的复制 (22:32)
视频：5-7 MySQL复制拓扑 (13:58)
视频：5-8 MySQL复制性能优化 (09:23)
视频：5-9 MySQL复制常见问题处理 (08:31)
视频：5-10 什么是高可用架构 (14:09)
视频：5-11 MMM架构介绍 (08:09)
视频：5-12 MMM架构实例演示（上） (09:16)试看
视频：5-13 MMM架构实例演示（下） (18:55)
视频：5-14 MMM架构的优缺点 (08:01)
视频：5-15 MHA架构介绍 (10:02)
视频：5-16 MHA架构实例演示(1) (13:11)
视频：5-17 MHA架构实例演示(2) (16:54)
视频：5-18 MHA架构优缺点 (05:14)
视频：5-19 读写分离和负载均衡介绍 (11:42)
视频：5-20 MaxScale实例演示 (18:25)
作业：5-21 讨论题MySQL主从复制为什么会有延迟，延迟又是如何产生
作业：5-22 实 *** 题请为某互联网项目设计9999%MySQL架构
作业：5-23 讨论题如何给一个已经存在的主从复制集群新增一个从节点
作业：5-24 讨论题给你三台数据库服务器，你如何设计它的高可用架构
第6章 数据库索引优化8 节 | 65分钟
介绍BTree索引和Hash索引，详细介绍索引的优化策略等等。
收起列表
视频：6-1 Btree索引和Hash索引 (20:09)
视频：6-2 安装演示数据库 (01:19)
视频：6-3 索引优化策略（上） (17:33)
视频：6-4 索引优化策略（中） (13:02)
视频：6-5 索引优化策略（下） (12:30)
作业：6-6 讨论题一列上建立了索引，查询时就一定会用到这个索引吗
作业：6-7 讨论题在定义联合索引时为什么需要注意联合索引中的顺序
作业：6-8 实 *** 题SQL建立索引，你会考虑那些因素
第7章 SQL查询优化9 节 | 62分钟
详细介绍慢查询日志及示例演示,MySQL查询优化器介绍及特定SQL的查询优化等。
收起列表
视频：7-1 获取有性能问题SQL的三种方法 (05:14)
视频：7-2 慢查询日志介绍 (08:57)
视频：7-3 慢查询日志实例 (08:27)
视频：7-4 实时获取性能问题SQL (02:21)
视频：7-5 SQL的解析预处理及生成执行计划 (16:02)
视频：7-6 如何确定查询处理各个阶段所消耗的时间 (09:35)
视频：7-7 特定SQL的查询优化 (10:34)
作业：7-8 讨论题如何跟据需要对一个大表中的数据进行删除或更新
作业：7-9 讨论题如何获取需要优化的SQL查询
第8章 数据库的分库分表5 节 | 48分钟
详细介绍数据库分库分表的实现原理及演示案例等。
收起列表
视频：8-1 数据库分库分表的几种方式 (04:34)
视频：8-2 数据库分片前的准备 (13:53)
视频：8-3 数据库分片演示(上) (11:40)
视频：8-4 数据库分片演示(下) (17:02)
作业：8-5 讨论题对于大表来说我们一定要进行分库分表吗
第9章 数据库监控7 节 | 29分钟
介绍数据库可用性监控、性能监控、MySQL主从复制监控等
收起列表
视频：9-1 数据库监控介绍 (04:46)
视频：9-2 数据库可用性监控 (07:20)
视频：9-3 数据库性能监控 (09:39)
视频：9-4 MySQL主从复制监控 (06:16)
作业：9-5 讨论题QPS是否可以真实的反映出数据库的负载情况
作业：9-6 讨论题如何正确评估数据库的当前负载状况
作业：9-7 实 *** 题开发一个简单监控脚本，监控mySQL数据库阻塞情况
那个叫二叉树啊
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
一、树的概述
树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。
（一）树的定义
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；
⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、Tn，而且，
这些集合的每一个又都是树。树T1、T2、Tn被称作根的子树(Subtree)。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2树的深度——组成该树各结点的最大层次，如上图，其深度为4；
3森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合就为森林；
4有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
5树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5
2
二叉树
1二叉树的基本形态：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)右子树为空的二叉树——(c)；
(4)左子树为空的二叉树——(d)；
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
viod leafnum(BTree T)
{
int count=0;//采用前序遍历的思想，count记录叶子节点总数；
int top=-1;//采用顺序栈
BNode p=T;
BNode Stack[MaxSize];//假设顺序栈容量足够大
Stack[++top]=p;//根节点入栈
while(p!=NULL||top!=-1)
{
while(p!=NULL)
{
if(p->lchild==NULL&&p->rchild==NULL)//满足叶子节点特性
count++;//叶子节点计数器+1；
else
{
if(p->rchild!=NULL)Stack[++top]=p->lchild;//p左子树非空则进栈
if(p->rchild!=NULL)Stack[++top]=p->rchild;//p右子树非空则进栈
}
}
if(top!=-1)
{
p=Stack[top];//出栈一个结点
top--;
}
}
return count;
}
了解mysql的索引类型的时候，我觉得按照以下4中方式划分逻辑是比较清晰的。
1存储结构 2物理存储 3作用字段 4功能
按照数据存储的结构可以分B树索引和hash索引。
又称为 BTREE 索引，目前大部分的索引都是采用 B-树索引来存储的。B-树索引是一个典型的数据结构。
基于这种树形数据结构，表中的每一行都会在索引上有一个对应值。因此，在表中进行数据查询时，可以根据索引值一步一步定位到数据所在的行。
查询必须从索引的最左边的列开始。
查询不能跳过某一索引列，必须按照从左到右的顺序进行匹配。
存储引擎不能使用索引中范围条件右边的列。
也称为散列索引或 HASH 索引。MySQL 目前仅有 MEMORY 存储引擎和 HEAP 存储引擎支持这类索引。
其中，MEMORY 存储引擎可以支持 B-树索引和 HASH 索引，且将 HASH 当成默认索引。
HASH 索引不是基于树形的数据结构查找数据，而是根据索引列对应的哈希值的方法获取表的记录行。
不能使用 HASH 索引排序。
HASH 索引只支持等值比较，如“=”“IN()”或“<=>”。
HASH 索引不支持键的部分匹配，因为在计算 HASH 值的时候是通过整个索引值来计算的。
聚集索引是按照所以把数据排好序了，所以一个表只能存在一个聚集索引，其它的都是非聚集索引。
因这个特性，聚集索引是查询数据范围的时候有很大的性能优势。
但是也需要注意的是如果频繁更新的列不适合设置为聚集索引，
原因很简单，每次更新都需要从新排序，频繁的更新给的压力也大。
如果不指定的话，默认主键为聚集索引。
一个表里除了一个聚集索引外其他的都是非聚集索引，虽然不能把数据按照索引排序，但是索引数据是可以排序的。
所以非聚集索引查询范围的时候是先找索引列的范围，再通过这个索引查询行的值。
单列索引即一个索引只包含单个列。
组合索引指在表的多个字段组合上创建的索引，只有在查询条件中使用了这些字段的左边字段时，索引才会被使用。使用组合索引时遵循最左前缀集合
Primary Key（聚集索引）：InnoDB存储引擎的表会存在主键（唯一非null），如果建表的时候没有指定主键，则会使用第一非空的唯一索引作为聚集索引，否则InnoDB会自动帮你创建一个不可见的、长度为6字节的row_id用来作为聚集索引。
Key（普通索引）：是MySQL中的基本索引类型，允许在定义索引的列中插入重复值和空值
Unique（唯一索引）：索引列的值必须唯一，但允许有空值。若是组合索引，则列值的组合必须唯一。
主键索引是一种特殊的唯一索引，不允许有空值。
既不是主键索引也不是唯一索引的一般索引。
FULLTEXT（全文索引）：全文索引类型为FULLTEXT，在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值。
全文索引可以在CHAR、VARCHAR或者TEXT类型的列上创建。
空间索引主要用于地理空间数据类型 GEOMETRY。
下面是 mysql官网给出的几个存储引擎和索引之间的关系 。
欢迎大家的意见和交流
email: li_mingxie@163com
一．gin索引需要安装第三方插件
yum install postgresql96-contrib -- 安装插件
find / -name extension --可以看到btree_gincontrol存在
create extension btree_gin; -- 添加索引
二测试数据基本属性介绍
总共使用3个表，表结构和数据量完全一致。
表数据量：10522369
表字段：id ,basic_acc_no,id_card,name,sex,telephone,json_t
1）索引的配置情况：
basic_account_info_al -- btree
basic_account_info_al2 --gin
basic_account_info_al3 -- btree multi
basic_account_info_al 单列索引 id，basic_acc_no，name,json_t
basic_account_info_al2 gin索引 (id,basic_acc_no,id_card,name),(json_t)
basic_account_info_al3 复合索引 (id,basic_acc_no),(name,id)(json_t,id)
basic_account_info_al 表达式索引 (json_t->>id)
basic_account_info_al2表达式索引 ((json_t->>'id'))
三．测试结果
1唯一值属性：索引字段都是唯一 id，basic_acc_no
查询语句
explain analyse select from basic_account_info_al2 where id = 29699221 ;
explain analyse select from basic_account_info_al where id = 29699221 ;
explain analyse select from basic_account_info_al3 where id = 29699221 ;
explain analyse select from basic_account_info_al2 where basic_acc_no = 'XFK2990134' ;
explain analyse select from basic_account_info_al where basic_acc_no = 'XFK2990134' ;
explain analyse select from basic_account_info_al3 where basic_acc_no = 'XFK2990134' ;
explain analyse select from basic_account_info_al2 where basic_acc_no = 'XFK9780134' and id = 29699221;
explain analyse select from basic_account_info_al where basic_acc_no = 'XFK9780134' and id = 29699221;
explain analyse select from basic_account_info_al3 where basic_acc_no = 'XFK9780134' and id = 29699221;
explain analyse select from basic_account_info_al2 where id = 29699221 and basic_acc_no = 'XFK9780134' ;
explain analyse select from basic_account_info_al where id = 29699221 and basic_acc_no = 'XFK9780134' ;
explain analyse select from basic_account_info_al3 where id = 29699221 and basic_acc_no = 'XFK9780134' ;
2重复值属性： name是有重复值的。
explain analyse select from basic_account_info_al where name ='张燕洪';
explain analyse select from basic_account_info_al3 where name ='张燕洪';
explain analyse select from basic_account_info_al2 where name ='张燕洪';
explain analyse select from basic_account_info_al2 where id = 24426014 and name = '周杨' ;
explain analyse select from basic_account_info_al where id = 24426014 and name = '周杨' ;
explain analyse select from basic_account_info_al3 where id = 24426014 and name = '周杨' ;
explain analyse select from basic_account_info_al2 where name = '周杨' and id = 24426014 ;
explain analyse select from basic_account_info_al where name = '周杨' and id = 24426014 ;
explain analyse select from basic_account_info_al3 where name = '周杨' and id = 24426014 ;
3jsonb属性
create index inx_gin_json on basic_account_info_al2 using gin (json_t);
create index inx_btree_json on basic_account_info_al (json_t);
create index inx_btree_2_js on basic_account_info_al3 (json_t,id );
explain analyse select from basic_account_info_al where json_t ='{"id": 21782879, "sex": 0, "name": "刘乐典"}';
explain analyse select from basic_account_info_al2 where json_t ='{"id": 21782879, "sex": 0, "name": "刘乐典"}';
explain analyse select from basic_account_info_al3 where json_t ='{"id": 21782879, "sex": 0, "name": "刘乐典"}';
explain analyse select from basic_account_info_al WHERE json_t @> '{"id": 21782879}';
explain analyse select from basic_account_info_al2 WHERE json_t @> '{"id": 21782879}';
explain analyse select from basic_account_info_al3 WHERE json_t @> '{"id": 21782879}';
explain analyse select from basic_account_info_al where (json_t->>id)= '24426014' ;
explain analyse select from basic_account_info_al2 where (json_t->>id)= '24426014' ;
explain analyse select from basic_account_info_al3 where (json_t->>id)='24426014' ;
4jsonb表达式索引
查询条件 表名 查询时使用的索引名称 查询时间（5次平均）/ms
(json_t->>id)= '24426014' basic_account_info_al inx_json_id 0040
basic_account_info_al3 inx_json_id_2 0039
explain analyse select from basic_account_info_al where (json_t->>id)= '24426014' ;
explain analyse select from basic_account_info_al2 where (json_t->>id)= '24426014' ;
四．获相同的结果使用Jsonb与btree对比
jsonb支持两种特有的GIN索引jsonb_ops和jsonb_path_ops。 jsonb_ops调用gin_extract_jsonb函数生成key，每个键和值都作为一个单独的索引项。而jsonb_path_ops使用函数gin_extract_jsonb_path抽取：只为每个值创建一个索引项。{“foo”:{“bar”,”baz”}}, jsonb_ops生成3个索引项，jsonb_path_ops由foo,bar,baz组合一个hash值作为一个索引项。jsonb_path_ops索引要比jsonb_ops的小很多，性能上也会有所提升。
create index inx_gin_patn_json ON publicbasic_account_info_al4 USING gin (json_t jsonb_path_ops); -- jsonb_path_ops
create index inx_gin_json on basic_account_info_al2 using gin (json_t); --jsonb_ops
1精确查询
2范围查询
下表显示了gin索引对于jsonb数据类型可使用的 *** 作符。
名称 索引数据类型 可索引 *** 作符
jsonb_ops jsonb & | @>
json_path_ops jsonb @>
注： & | 索引key是否包含在jsonb中
对于范围(json_t->>'id')< 20000079，这样的条件 gin索引不起作用， 这里采用表达式索引方式，查询条件的两边数据类型相同才可以做索引查询，否则全表扫描。
CREATE INDEX inx_json_id_2 ON publicbasic_account_info_al2 USING btree (((json_t->>'id')::int));
总结： 当仅有一个条件查询时，gin索引与btree索引的性能差异不大，但有多个条件查询时，gin,btree单
列索引没有btree复合索引的性能高。jsonb是以二进制格式存储且不保证键的顺序。可以使用表达式索引指定到jsonb的具体键值，但是如果不能提前知道查询数据中的哪个键，确定定义GIN索引和使用@>（或者其他有利于索引的 *** 作符）查询。
五．jsonb添加数据属性
例如：
{"id":20000241,"name":"陈敏","sex":1} -> {"age":"18","id":20000241,"name":"陈敏","sex":1}
一旦创建了索引，就不需要进一步的干预：当表被修改时，系统将更新索引，当执行计划认为使用索引比顺序的表扫描更有效的时候，它会使用索引。
UPDATE basic_account_info_al4 SET json_t = json_t || '{"age":"18"}'::jsonb; -- 更新语句
gin索引名称 索引方式 修改前大小 修改后大小 带索引更新时间
inx_gin_patn_json jsonb_path_ops 574M 615M 643561004 ms
inx_gin_json jsonb_ops 665M 695M 时间过长超过1h
jsonb_ops方式建立的索引大量更新时，执行时间太长。当插入更新时gin索引比较慢，如果要向一张大表中插入大量数据时，最好先把gin索引删除，插入数据后再重建索引。
当json_t为{"id":20000241,"name":"陈敏","sex":1} 数据量为10522369 创建gin索引时间
130372955 ms
当json_t为{"age":"18","id":20000241,"name":"陈敏","sex":1} 数据量为10522369 创建gin索引时间
148971011 ms
七个权值3 3 7 7 11 13 17
(1) 从小到大排序 3 3 7 7 11 13 17 (这是有序序列)
(2) 每次提取最小的两个节点,取节点3和另一个节点3,组成新节点N6,其权值=3+3=6,
取数值较小的节点作为左分支,两个权值都是3,一个为左分支,另个为右分支
(3) 将新节点N6放入有序序列,保持从小到大排序:
N6 7 7 11 13 17 (两个节点3已经提取掉)
(4) 重复步骤(2),提取最小的两个节点,N6与节点7组成新节点N13,其权值=6+7=13,
N6的数值较小,作为左分支,节点7就作为右分支
(5) 将新节点N13放入有序序列,保持从小到大排序:
7 11 13 N13 17 (注意,要将新节点N13排在节点13的后面)
(6) 重复步骤(2),提取最小的两个节点,节点7与节点11组成新节点N18,其权值=7+11=18,
节点7的数值较小,作为左分支,节点11就作为右分支
(7) 将新节点N18放入有序序列,保持从小到大排序:
13 N13 17 N18
(8) 重复步骤(2),提取最小的两个节点,节点13与N13组成新节点N26,其权值=13+13=26,
节点13作为左分支,N13就作为右分支
(9) 将新节点N26放入有序序列,保持从小到大排序:
17 N18 N26
(10)重复步骤(2),完成剩下的节点,最后,得到"哈夫曼树":
N61
/ \
N26 N35
/ \ / \
13 N13 17 N18
/ \ / \
N6 7 7 11
/ \
3 3
根节点N61到节点17的路径长度是2,节点17的带权路径长度是172
根节点N61到节点13的路径长度是2,节点13的带权路径长度是132
根节点N61到节点11的路径长度是3,节点11的带权路径长度是113
如此类推,可以得出其它节点的带权路径长度
所以,哈夫曼树的带权路径长度WPL等于
172 + 132 + 113 + 73 + 73 + 34 + 34 = 159
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1
从根节点N61到节点17,先经历右分支,再经历左分支,节点6的编码就是10
从根节点N61到节点13,先后经历两次左分支,节点13的编码就是00
从根节点N61到节点11,先后经历三次右分支,节点11的编码就是111
如此类推,可以得出所有的节点的"哈夫曼编码":
权值17: 10
权值13: 00
权值11: 111
权值 7: 011
权值 7: 110
权值 3: 0100
权值 3: 0101
//C语言测试程序
//输入构造哈夫曼树中带权叶子结点数n：7
//输入5个整数作为权值：17 13 11 7 7 3 3
//可以得出哈夫曼树的带权路径长度,以及哈夫曼编码
#include
#include
typedef int ElemType;
struct BTreeNode
{
ElemType data;
struct BTreeNode left;
struct BTreeNode right;
};
//1、输出二叉树，可在前序遍历的基础上修改。
// 采用广义表格式，元素类型为int
void PrintBTree_int(struct BTreeNode BT)
{
if (BT != NULL)
{
printf("%d", BT->data); //输出根结点的值
if (BT->left != NULL || BT->right != NULL)
{
printf("(");
PrintBTree_int(BT->left); //输出左子树
if (BT->right != NULL)
printf(",");
PrintBTree_int(BT->right); //输出右子树
printf(")");
}
}
}
//2、根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针
struct BTreeNode CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode b, q;
b = malloc(nsizeof(struct BTreeNode));
//初始化b指针数组，使每个指针元素指向a数组中对应的元素结点
for (i = 0; i < n; i++)
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树
{
//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
int k1 = -1, k2;
//让k1初始指向森林中第一棵树，k2指向第二棵
for (j = 0; j < n; j++)
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
//从当前森林中求出最小权值树和次最小
for (j = k2; j < n; j++)
{
if (b[j] != NULL)
{
if (b[j]->data b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data b[k2]->data)
k2 = j;
}
}
//由最小权值树和次最小权值树建立一棵新树，q指向树根结点
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置
b[k2] = NULL;//k2位置为空
}
free(b); //删除动态建立的数组b
return q; //返回整个哈夫曼树的树根指针
}
//3、求哈夫曼树的带权路径长度
ElemType WeightPathLength(struct BTreeNode FBT, int len)//len初始为0
{
if (FBT == NULL) //空树返回0
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点
{
printf("+ %d %d ",FBT->data,len);
return FBT->data len;
}
else //访问到非叶子结点，进行递归调用，
{ //返回左右子树的带权路径长度之和，len递增
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）
void HuffManCoding(struct BTreeNode FBT, int len)//len初始值为0
{
//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一
static int a[10];
int i;
//访问到叶子结点时输出其保存在数组a中的0和1序列编码
if (FBT != NULL)
{
if (FBT->left == NULL && FBT->right == NULL)
{
printf("权值为%d的编码：", FBT->data);
for (i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
else //访问到非叶子结点时分别向左右子树递归调用，
{ //并把分支上的0、1编码保存到数组a的对应元素中，
//向下深入一层时len值增1
a[len] = 0;
HuffManCoding(FBT->left, len + 1);
a[len] = 1;
HuffManCoding(FBT->right, len + 1);
}
}
}
int main()
{
int n, i;
ElemType a;
struct BTreeNode fbt;
printf("输入构造哈夫曼树中带权叶子结点数n：");
while(1)
{
scanf("%d", &n);
if (n > 1)
break;
else
printf("重输n值：");
}
a = malloc(nsizeof(ElemType));
printf("输入%d个整数作为权值：", n);
for (i = 0; i < n; i++)
scanf(" %d", &a[i]);
fbt = CreateHuffman(a, n);
printf("广义表形式的哈夫曼树：");
PrintBTree_int(fbt);
printf("\n");
printf("哈夫曼树的带权路径长度：\n");
printf("=");
printf("\n=%d\n", WeightPathLength(fbt, 0));
printf("树中每个叶子结点的哈夫曼编码：\n");
HuffManCoding(fbt, 0);
return 0;
}
// 二叉树的先序遍历序列: A B C E D F H G I J
// 二叉树的中序遍历序列: E C B H F D J I G A
// 二叉树的后序遍历序列: E C H F J I G D B A
#include "stdioh"
#include "stdlibh"
struct tree
{
char data;
struct tree left;
struct tree right;
};
typedef struct tree treenode;
typedef treenode btree;
btree createbtree(char data,int pos,int maxPos) //递归创建法
{
btree newnode;
if(data[pos]==0 || pos>maxPos)
{
return NULL;
}
else
{
newnode=(btree)malloc(sizeof(treenode));
newnode->data=data[pos];
newnode->left=createbtree(data,2pos,maxPos);
newnode->right=createbtree(data,2pos+1,maxPos);
return newnode;
}
}
void inorder(btree ptr)
{
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%C ",ptr->data);
inorder(ptr->right);
}
}
void preorder(btree ptr)
{
if(ptr!=NULL)
{
printf("%C ",ptr->data);
preorder(ptr->left);
preorder(ptr->right);
}
}
void postorder(btree ptr)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
printf("%C ",ptr->data);
}
}
int main()
{
btree root=NULL;
int i;
char data[64]={0,'A','B',0,'C','D',0,0,
'E',0,'F','G',0,0,0,0,
0,0,0,0,'H',0,'I',0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,'J',0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
root=createbtree(data,1,63);
printf("二叉树的顺序存储内容:\n");
for(i=1;i<64;i++)
{
if(data[i]==0)
{
printf("^ ");
}
else
{
printf("%C ",data[i]);
}
if(i % 8 == 7) printf("\n");
}
printf("\n二叉树的先序遍历序列: ");
preorder(root);
printf("\n二叉树的中序遍历序列: ");
inorder(root);
printf("\n二叉树的后序遍历序列: ");
postorder(root);
printf("\n");
return 0;
}
以上就是关于扛得住的MySQL数据库架构全部的内容，包括:扛得住的MySQL数据库架构、求数据结构 B-树与B+树及其 *** 作的代码（C语言版）、数据结构 求叶子个数等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）