zhfang

zhfang 查看完整档案

北京编辑北京邮电大学  |  计算机科学与技术 编辑  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

个人动态

zhfang 收藏了文章 · 2月28日

IO模型浅析-阻塞、非阻塞、IO复用、信号驱动、异步IO、同步IO

最近看到OVS用户态的代码,在接收内核态信息的时候,使用了Epoll多路复用机制,对其十分不解,于是从网上找了一些资料,学习了一下《UNIX网络变成卷1:套接字联网API》这本书对应的章节,网上虽然关于该主题的博文很多,并且讲解的很详细,但是在这里还是做一个学习笔记,记录一下自己的想法。

IO模型

在《UNIX网络变成卷1:套接字联网API》这本书中,提到了五种I/O模型,分别为:阻塞式I/O、非阻塞式I/O、I/O复用(Epoll、select都是一种I/O复用机制),信息驱动式I/O、异步I/O,下面具体的一一介绍。

阻塞式I/O模型

阻塞,顾名思义,当进程在等待数据时,若该数据一直没有产生,则该进程将一直等待,直到等待的数据产生为止,这个过程中进程的状态是阻塞的。

![1536649297449](C:UsersyearsjAppDataLocalTemp1536649297449.png)

如上图所示,在linux中,用户态进程调用recvfrom系统调用接收数据,当前内核中并没有准备好数据,该用户态进程将一直在此等待,不会进行其他的操作,待内核态准备好数据,将数据从内核态拷贝到用户空间内存,然后recvfrom返回成功的指示,此时用户态进行才解除阻塞的状态,处理收到的数据。

从上述过程可以看出,用户态接收内核态数据的时候,主要有两个过程:内核态获得数据-->将数据从内核态的内存空间中复制到用户态进程的缓冲区中

非阻塞式I/O模型

在非阻塞式I/O模型中,当进程等待内核的数据,而当该数据未到达的时候,进程会不断询问内核,直到内核准备好数据。

![1536653838706](C:UsersyearsjAppDataLocalTemp1536653838706.png)

如上图,用户态进程调用recvfrom接收数据,当前并没有数据报文产生,此时recvfrom返回EWOULDBLOCK,用户态进程会一直调用recvfrom询问内核,待内核准备好数据的时候,之后用户态进程不再询问内核,待数据从内核复制到用户空间,recvfrom成功返回,用户态进程开始处理数据。

需要注意的是,当数据从内核复制到用户空间中的这一段时间中,用户态进程是处于阻塞的状态的。

非阻塞式I/O模型,个人觉得这个名字可能有点混淆,并不是和阻塞式模型是完全对立的,不是说进程等不到数据,就去做别的事情,恰恰进程这个时候一直在原地等待数据的到来,与阻塞式模型不同的是,非阻塞相当于进程一直在敲门问“数据好了么,快给我”,然后房门后的人说“没有准备好,请稍后!”,这个过程是一种轮询的状态,而阻塞式是佛系的态度,敲了一次门,房门后的人没有给任何回应,于是就去睡觉,啥都不做,直到房门后的人做出响应叫醒他,进程才去做下一步动作。

I/O复用模型

在ovs的用户态源码里,就用到了I/O复用模型,在计算机网络里面,有很多关于“复用”的用法,比如多路复用,意思就是本来一条链路上一次只能传输一个数据流,如果要实现两个源之间多条数据流同时传输,那就得需要多条链路了,但是复用技术可以通过将一条链路划分频率,或者划分传输的时间,使得一条链路上可以同时传输多条数据流。

![1536655348189](C:UsersyearsjAppDataLocalTemp1536655348189.png)

套用到I/O复用模型上,可以对应到如下应用场景:如果一个进程需要等到多种不同的消息,那么一般的做法就是开启多条线程,每个线程接收一类消息,如果每个线程都是采用阻塞式I/O模型,那么每个线程在消息未产生的时候就会阻塞,也就是说在多线程中使用阻塞式I/O。I/O复用就是基于上述的场景中,无需采用多线程监听消息的方式,进程直接监听所有的消息类型,这其中就涉及到select、poll、epoll等不同的方法。

如上图所示,用户态进程采用select的方法,通过select可以等待多个不同类型的消息,如果其中有一个类型的消息准备好,则select会返回信息,然后用户态进程调用recvfrom接收数据。

可以将select复用机制看作是一个描述符集合的管理,进程通过向这个集合中放入不同的描述符,用来等待不同的消息产生,然后通过select统一的进行管理,让其可以同时等待这个集合中任意一个事件的产生。

I/O复用和阻塞式I/O很相似,不同的是,I/O复用等待多类事件,阻塞式I/O只等待一类事件,另外,在I/O复用中,会产生两个系统调用(如上图,select和recvfrom),而阻塞式I/O只产生一个系统调用。那么这就涉及到具体的性能问题,当只存在一类事件的时候,使用阻塞式I/O模型的性能会更好,当存在多种不同类型的事件时,I/O复用的性能要好的多,因为阻塞式I/O模型只能监听一类事件,所以这个时候需要使用多线程进行处理。

信号驱动式I/O模型

在信号驱动式I/O模型中,与阻塞式和非阻塞式有了一个本质的区别,那就是用户态进程不再等待内核态的数据准备好,直接可以去做别的事情。

![1536662911379](C:UsersyearsjAppDataLocalTemp1536662911379.png)

如上图所示,当需要等待数据的时候,首先用户态会向内核发送一个信号,告诉内核我要什么数据,然后用户态就不管了,做别的事情去了,而当内核态中的数据准备好之后,内核立马发给用户态一个信号,说”数据准备好了,快来查收“,用户态进程收到之后,立马调用recvfrom,等待数据从内核空间复制到用户空间,待完成之后recvfrom返回成功指示,用户态进程才处理别的事情。

通过上面的图,可以看出信号驱动式I/O模型有种异步操作的赶脚,但是在将数据从内核复制到用户空间这段时间内用户态进程是阻塞的

异步I/O模型

异步I/O模型相对于信号驱动式I/O模型就更彻底了。

![1536664199720](C:UsersyearsjAppDataLocalTemp1536664199720.png)

如上图,首先用户态进程告诉内核态需要什么数据(上图中通过aio_read),然后用户态进程就不管了,做别的事情,内核等待用户态需要的数据准备好,然后将数据复制到用户空间,此时才告诉用户态进程,”数据都已经准备好,请查收“,然后用户态进程直接处理用户空间的数据。

在复制数据到用户空间这个时间段内,用户态进程也是不阻塞的

同步I/O

《UNIX网络变成卷1:套接字联网API》这本书中,并没有把同步I/O作为一种单独的I/O模型来说明,在没有阅读这些资料之前,我一直认为阻塞式I/O等同于同步I/O,非阻塞式I/O等同于异步I/O,可见不能单纯的通过字面意思就进行判断。

通过对上述几种I/O模型的描述中,可以得到一个结论:阻塞式I/O、非阻塞式I/O、I/O复用模型是同步I/O模型,因为在等待数据的过程中,这三种模型中的进程都没有去做别的事情,即便是非阻塞式的轮询,也可以看作是一种同步。

同时书中也认为信号驱动式I/O模型是同步I/O,书中说到:POSIX将同步IO操作定义为“导致请求进程阻塞,直到I/O操作完成”,而书中认为在信号驱动式I/O模型中等待数据的那段时间不算是真正的I/O操作(因为没有调用I/O相关的系统调用),而数据从内核复制到用户空间才是真正的I/O操作(这个时候调用了recvfrom系统调用)。

I/O模型比较

书中的这张图表述的非常清楚,从等待数据和数据复制这两个时间段,指出了不同I/O模型的区别,这里不再赘述。

![1536665393236](C:UsersyearsjAppDataLocalTemp1536665393236.png)

总结

从网上看了很多资料,不同的博主对这五个模型总结的情况不同,无一例外,基本都采用一个生活场景来描述他们的不同,但是我个人觉得有些场景描述太过简单,没有将不同模型的区别描述完全,在这里我也举一个生活中的场景作为总结,当然这只是我自己的想法,不妥之处评论区可以指出。

我们去餐厅吃饭,会经过以下几个步骤:首先根据菜单点菜,然后等待厨房准备好,接着服务员上菜。在这个场景中,等待厨房准备菜肴等同于等待数据,服务员上菜等同于将数据从内核复制到用户空间,你就是用户态进程了,服务员和饭店看作是内核态的进程。

阻塞式I/O模型:只点一个菜,然后在餐桌上开始等待,在这个过程中什么事都不干,等服务员把菜上到桌子上之后才开始大快朵颐。

非阻塞式I/O模型:只点一个菜,然后开始等待,啥事都不做,等了一会儿然后就去问服务员,“我的菜好了吗?”,没好接着等待,过了一会儿然后又跑去问....重复这个过程,直到服务员说“亲,你的菜好了,我现在给您送桌上去”,然后你坐在桌子上,等待服务员把饭菜送到你的餐桌上,才开始吃饭。

I/O复用模型:你点了很多菜,然后开始等待,某个时刻其中一个菜或者多个菜厨房里同时好了,服务员跑过来说,“亲,您的有些菜好了,要现在上桌么?”, 你回答,现在就上,于是服务员上一个菜(服务员一次只能上一个菜),你就吃完一个,上一个你就吃完一个。。。

信号驱动式I/O模型:只点一个菜,然后给服务员留下手机,告诉他菜准备好了打个电话给你,先不要上菜,然后你就出去玩耍了,等到菜好了,服务员手机通知你,你立马回到了餐厅,对服务员说“你现在可以上菜了”,于是你在餐桌上等待服务员把菜送上来,然后吃饭。

异步I/O模型:只点一个菜,然后给服务员留下手机,告诉他菜准备好了先上菜,菜上桌了打电话给你,然后你就出去玩耍了,等到菜上桌了,服务员手机通知你,你立马回到了餐桌,开始吃饭。

参考资料

UNIX网络变成卷1:套接字联网API
网络IO之阻塞、非阻塞、同步、异步总结
IO - 同步,异步,阻塞,非阻塞 (亡羊补牢篇)

作者:yearsj
转载请注明出处:https://segmentfault.com/a/11...
查看原文

zhfang 收藏了文章 · 2月27日

一张图搞懂MySQL的索引失效

索引对于MySQL而言,是非常重要的篇章。索引知识点也巨多,要想掌握透彻,需要逐个知识点一一击破,今天来先来聊聊哪些情况下会导致索引失效。

图片总结版

索引失效的情况

全值匹配(索引最佳)

explain select * from user where name = 'zhangsan' and age = 20 and pos = 'cxy' and phone = '18730658760';

索引失效的情况

和索引顺序无关,MySQL底层的优化器会进行优化,调整索引的顺序
explain select * from user where name = 'zhangsan' and age = 20 and pos = 'cxy' and phone = '18730658760';

索引失效的情况

1、违反最左前缀法则

如果索引有多列,要遵守最左前缀法则
即查询从索引的最左前列开始并且不跳过索引中的列
explain select * from user where age = 20 and phone = '18730658760' and pos = 'cxy';

索引失效的情况

2、在索引列上做任何操作

如计算、函数、(自动or手动)类型转换等操作,会导致索引失效从而全表扫描
explain select * from user where left(name,5) = 'zhangsan' and age = 20 and phone = '18730658760';

索引失效的情况

3、索引范围条件右边的列

索引范围条件右边的索引列会失效
explain select * from user where name = 'zhangsan' and age > 20 and pos = 'cxy';

索引失效的情况

4、尽量使用覆盖索引

只访问索引查询(索引列和查询列一致),减少select*
explain select name,age,pos,phone from user where age = 20;

索引失效的情况

5、使用不等于(!=、<>)

mysql在使用不等于(!=、<>)的时候无法使用索引会导致全表扫描(除覆盖索引外)
explain select * from user where age != 20;
explain select * from user where age <> 20;

索引失效的情况

索引失效的情况

6、like以通配符开头('%abc')

索引失效
explain select * from user where name like '%zhangsan';

索引失效的情况

索引生效
explain select * from user where name like 'zhangsan%';

索引失效的情况

7、字符串不加单引号索引失效

explain select * from user where name = 2000;

索引失效的情况

8、or连接

少用or
explain select * from user where name = '2000' or age = 20 or pos ='cxy';

索引失效的情况

9、order by

正常(索引参与了排序)
explain select * from user where name = 'zhangsan' and age = 20 order by age,pos;
备注:索引有两个作用:排序和查找

索引失效的情况

导致额外的文件排序(会降低性能)
explain select name,age from user where name = 'zhangsan' order by pos;//违反最左前缀法则
explain select name,age from user where name = 'zhangsan' order by pos,age;//违反最左前缀法则
explain select * from user where name = 'zhangsan' and age = 20 order by created_time,age;//含非索引字段

索引失效的情况

索引失效的情况

索引失效的情况

10、group by

正常(索引参与了排序)
explain select name,age from user where name = 'zhangsan' group by age;
备注:分组之前必排序(排序同order by)

索引失效的情况

导致产生临时表(会降低性能)
explain select name,pos from user where name = 'zhangsan' group by pos;//违反最左前缀法则
explain select name,age from user where name = 'zhangsan' group by pos,age;//违反最左前缀法则
explain select name,age from user where name = 'zhangsan' group by age,created_time;//含非索引字段

索引失效的情况

索引失效的情况

索引失效的情况

使用的示例数据

mysql> show create table user \G
******************************************************
       Table: user
Create Table: CREATE TABLE `user` (
  `id` int(10) NOT NULL AUTO_INCREMENT,
  `name` varchar(20) DEFAULT NULL,
  `age` int(10) DEFAULT '0',
  `pos` varchar(30) DEFAULT NULL,
  `phone` varchar(11) DEFAULT NULL,
  `created_time` datetime DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_name_age_pos_phone` (`name`,`age`,`pos`,`phone`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
查看原文

zhfang 关注了用户 · 2月27日

张德Talk @zhangdejian

每日精进,致力于成为全栈工程师!

关注 623

zhfang 收藏了文章 · 2月27日

一张图彻底搞懂MySQL的 explain

explain关键字可以模拟MySQL优化器执行SQL语句,可以很好的分析SQL语句或表结构的性能瓶颈。

explain的用途

1. 表的读取顺序如何
2. 数据读取操作有哪些操作类型
3. 哪些索引可以使用
4. 哪些索引被实际使用
5. 表之间是如何引用
6. 每张表有多少行被优化器查询
......

explain的执行效果

mysql> explain select * from subject where id = 1 \G
******************************************************
           id: 1
  select_type: SIMPLE
        table: subject
   partitions: NULL
         type: const
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: const
         rows: 1
     filtered: 100.00
        Extra: NULL
******************************************************

explain包含的字段

1. id //select查询的序列号,包含一组数字,表示查询中执行select子句或操作表的顺序
2. select_type //查询类型
3. table //正在访问哪个表
4. partitions //匹配的分区
5. type //访问的类型
6. possible_keys //显示可能应用在这张表中的索引,一个或多个,但不一定实际使用到
7. key //实际使用到的索引,如果为NULL,则没有使用索引
8. key_len //表示索引中使用的字节数,可通过该列计算查询中使用的索引的长度
9. ref //显示索引的哪一列被使用了,如果可能的话,是一个常数,哪些列或常量被用于查找索引列上的值
10. rows //根据表统计信息及索引选用情况,大致估算出找到所需的记录所需读取的行数
11. filtered //查询的表行占表的百分比
12. Extra //包含不适合在其它列中显示但十分重要的额外信息

图片版

一张图搞定explain

文字版

id字段

1. id相同
执行顺序从上至下
例子:
explain select subject.* from subject,student_score,teacher where subject.id = student_id and subject.teacher_id = teacher.id;
读取顺序:subject > teacher > student_score

一张图搞定 explain

2. id不同
如果是子查询,id的序号会递增,id的值越大优先级越高,越先被执行
例子:
explain select score.* from student_score as score where subject_id = (select id from subject where teacher_id = (select id from teacher where id = 2));
读取顺序:teacher > subject > student_score

一张图搞定 explain

3. id相同又不同
id如果相同,可以认为是一组,从上往下顺序执行
在所有组中,id值越大,优先级越高,越先执行
例子:
explain select subject.* from subject left join teacher on subject.teacher_id = teacher.id
 -> union 
 -> select subject.* from subject right join teacher on subject.teacher_id = teacher.id;
 读取顺序:2.teacher > 2.subject > 1.subject > 1.teacher

一张图搞定 explain

select_type字段

1. SIMPLE
简单查询,不包含子查询或Union查询
例子:
explain select subject.* from subject,student_score,teacher where subject.id = student_id and subject.teacher_id = teacher.id;

一张图搞定 explain

2. PRIMARY
查询中若包含任何复杂的子部分,最外层查询则被标记为主查询
例子:
explain select score.* from student_score as score where subject_id = (select id from subject where teacher_id = (select id from teacher where id = 2));

一张图搞定 explain

3. SUBQUERY
在select或where中包含子查询
例子:
explain select score.* from student_score as score where subject_id = (select id from subject where teacher_id = (select id from teacher where id = 2));

一张图搞定 explain

4. DERIVED
在FROM列表中包含的子查询被标记为DERIVED(衍生),MySQL
会递归执行这些子查询,把结果放在临时表中
备注:
MySQL5.7+ 进行优化了,增加了derived_merge(派生合并),默认开启,可加快查询效率
5. UNION
若第二个select出现在uion之后,则被标记为UNION
例子:
explain select subject.* from subject left join teacher on subject.teacher_id = teacher.id
 -> union 
 -> select subject.* from subject right join teacher on subject.teacher_id = teacher.id;

一张图搞定 explain

6. UNION RESULT
从UNION表获取结果的select
例子:
explain select subject.* from subject left join teacher on subject.teacher_id = teacher.id
 -> union 
 -> select subject.* from subject right join teacher on subject.teacher_id = teacher.id;

一张图搞定 explain

type字段

NULL>system>const>eq_ref>ref>fulltext>ref_or_null>index_merge>unique_subquery>index_subquery>range>index>ALL //最好到最差
备注:掌握以下10种常见的即可
NULL>system>const>eq_ref>ref>ref_or_null>index_merge>range>index>ALL
1. NULL
MySQL能够在优化阶段分解查询语句,在执行阶段用不着再访问表或索引
例子:
explain select min(id) from subject;

一张图搞定 explain

2. system
表只有一行记录(等于系统表),这是const类型的特列,平时不大会出现,可以忽略
3. const
表示通过索引一次就找到了,const用于比较primary key或uique索引,因为只匹配一行数据,所以很快,如主键置于where列表中,MySQL就能将该查询转换为一个常量
例子:
explain select * from teacher where teacher_no = 'T2010001';

一张图搞定 explain

4. eq_ref
唯一性索引扫描,对于每个索引键,表中只有一条记录与之匹配,常见于主键或唯一索引扫描
例子:
explain select subject.* from subject left join teacher on subject.teacher_id = teacher.id;

一张图搞定 explain

5. ref
非唯一性索引扫描,返回匹配某个单独值的所有行
本质上也是一种索引访问,返回所有匹配某个单独值的行
然而可能会找到多个符合条件的行,应该属于查找和扫描的混合体
例子:
explain select subject.* from subject,student_score,teacher where subject.id = student_id and subject.teacher_id = teacher.id;

一张图搞定 explain

6. ref_or_null
类似ref,但是可以搜索值为NULL的行
例子:
explain select * from teacher where name = 'wangsi' or name is null;

一张图搞定 explain

7. index_merge
表示使用了索引合并的优化方法
例子:
explain select * from teacher where id = 1 or teacher_no = 'T2010001' .

一张图搞定 explain

8. range
只检索给定范围的行,使用一个索引来选择行,key列显示使用了哪个索引
一般就是在你的where语句中出现between、<>、in等的查询。
例子:
explain select * from subject where id between 1 and 3;

一张图搞定 explain

9. index
Full index Scan,Index与All区别:index只遍历索引树,通常比All快
因为索引文件通常比数据文件小,也就是虽然all和index都是读全表,但index是从索引中读取的,而all是从硬盘读的。
例子:
explain select id from subject;

一张图搞定 explain

10. ALL
Full Table Scan,将遍历全表以找到匹配行
例子:
explain select * from subject;

一张图搞定 explain

table字段

数据来自哪张表

possible_keys字段

显示可能应用在这张表中的索引,一个或多个
查询涉及到的字段若存在索引,则该索引将被列出,但不一定被实际使用

key字段

 实际使用到的索引,如果为NULL,则没有使用索引
查询中若使用了覆盖索引(查询的列刚好是索引),则该索引仅出现在key列表

key_len字段

 表示索引中使用的字节数,可通过该列计算查询中使用的索引的长度
在不损失精确度的情况下,长度越短越好
key_len显示的值为索引字段最大的可能长度,并非实际使用长度
即key_len是根据定义计算而得,不是通过表内检索出的

ref字段

 显示索引的哪一列被使用了,如果可能的话,是一个常数,哪些列或常量被用于查找索引列上的值

rows字段

 根据表统计信息及索引选用情况,大致估算出找到所需的记录所需读取的行数

partitions字段

 匹配的分区

filtered字段

 查询的表行占表的百分比

Extra字段

 包含不适合在其它列中显示但十分重要的额外信息
1. Using filesort
说明MySQL会对数据使用一个外部的索引排序,而不是按照表内的索引顺序进行读取
MySQL中无法利用索引完成的排序操作称为“文件排序”
例子:
explain select * from subject order by name;

一张图搞定 explain

2. Using temporary
使用了临时表保存中间结果,MySQL在对结果排序时使用临时表,常见于排序order by 和分组查询group by
例子:
explain select subject.* from subject left join teacher on subject.teacher_id = teacher.id
 -> union 
 -> select subject.* from subject right join teacher on subject.teacher_id = teacher.id;

一张图搞定 explain

3. Using index
表示相应的select操作中使用了覆盖索引(Covering Index),避免访问了表的数据行,效率不错!
如果同时出现using where,表明索引被用来执行索引键值的查找
如果没有同时出现using where,表明索引用来读取数据而非执行查找动作
例子:
explain select subject.* from subject,student_score,teacher where subject.id = student_id and subject.teacher_id = teacher.id;
备注:
覆盖索引:select的数据列只用从索引中就能够取得,不必读取数据行,MySQL可以利用索引返回select列表中的字段,而不必根据索引再次读取数据文件,即查询列要被所建的索引覆盖

一张图搞定 explain

4. Using where
使用了where条件
例子:
explain select subject.* from subject,student_score,teacher where subject.id = student_id and subject.teacher_id = teacher.id;

一张图搞定 explain

5. Using join buffer
使用了连接缓存
例子:
explain select student.*,teacher.*,subject.* from student,teacher,subject;

一张图搞定 explain

6. impossible where
where子句的值总是false,不能用来获取任何元组
例子:
explain select * from teacher where name = 'wangsi' and name = 'lisi';

一张图搞定 explain

7. distinct
一旦mysql找到了与行相联合匹配的行,就不再搜索了
例子:
explain select distinct teacher.name from teacher left join subject on teacher.id = subject.teacher_id;

一张图搞定 explain

8. Select tables optimized away
SELECT操作已经优化到不能再优化了(MySQL根本没有遍历表或索引就返回数据了)
例子:
explain select min(id) from subject;

一张图搞定 explain

使用的数据表

create table subject(
 -> id int(10) auto_increment,
 -> name varchar(20),
 -> teacher_id int(10),
 -> primary key (id),
 -> index idx_teacher_id (teacher_id));//学科表
 
create table teacher(
 -> id int(10) auto_increment,
 -> name varchar(20),
 -> teacher_no varchar(20),
 -> primary key (id),
 -> unique index unx_teacher_no (teacher_no(20)));//教师表
 
 create table student(
 -> id int(10) auto_increment,
 -> name varchar(20),
 -> student_no varchar(20),
 -> primary key (id),
 -> unique index unx_student_no (student_no(20)));//学生表
 
 create table student_score(
 -> id int(10) auto_increment,
 -> student_id int(10),
 -> subject_id int(10),
 -> score int(10),
 -> primary key (id),
 -> index idx_student_id (student_id),
 -> index idx_subject_id (subject_id));//学生成绩表
 
 alter table teacher add index idx_name(name(20));//教师表增加名字普通索引
 
 数据填充:
 insert into student(name,student_no) values ('zhangsan','20200001'),('lisi','20200002'),('yan','20200003'),('dede','20200004');
 
 insert into teacher(name,teacher_no) values('wangsi','T2010001'),('sunsi','T2010002'),('jiangsi','T2010003'),('zhousi','T2010004');
 
 insert into subject(name,teacher_id) values('math',1),('Chinese',2),('English',3),('history',4);
 
insert into student_score(student_id,subject_id,score) values(1,1,90),(1,2,60),(1,3,80),(1,4,100),(2,4,60),(2,3,50),(2,2,80),(2,1,90),(3,1,90),(3,4,100),(4,1,40),(4,2,80),(4,3,80),(4,5,100);
查看原文

zhfang 发布了文章 · 1月21日

实现 Trie (前缀树)

class Trie {
    class TrieNode {
        private boolean isEnd;
        private TrieNode[] links;

        TrieNode() {
            links = new TrieNode[26];
        }

        public boolean containsKey(char ch) {
            return links[ch-'a'] != null;
        }

        public TrieNode get(char ch) {
            return links[ch-'a'];
        }

        public void put(char ch, TrieNode node) {
            links[ch-'a'] = node;
        }

        public void setEnd() {
            isEnd = true;
        }

        public boolean isEnd() {
            return isEnd;
        }
    }

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for(char ch : word.toCharArray()) {
            if(!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for(char ch : word.toCharArray()) {
            if(!node.containsKey(ch)) {
                return false;
            }
            node = node.get(ch);
        }
        return node.isEnd();
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for(char ch : prefix.toCharArray()) {
            if(!node.containsKey(ch)) {
                return false;
            }
            node = node.get(ch);
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
查看原文

赞 0 收藏 0 评论 0

zhfang 发布了文章 · 1月19日

leetcode 鸡蛋掉落

class Solution {
    public int calc(int K, int T) {
        if(K==1 || T==1) return T+1;
        return calc(K-1, T-1) + calc(K, T-1);
    }

    public int superEggDrop(int K, int N) {
        int T = 1;
        while(calc(K, T) < N+1) {
            T++;
        }
        return T;
    }
}
查看原文

赞 0 收藏 0 评论 0

zhfang 发布了文章 · 1月13日

二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}
查看原文

赞 0 收藏 0 评论 0

zhfang 发布了文章 · 1月13日

对称二叉树-递归和迭代

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode a, TreeNode b) {
        if(a == null && b == null) {
            return true;
        }
        if(a == null || b == null) {
            return false;
        }
        return  a.val == b.val && check(a.left, b.right) && check(a.right, b.left);
    }
}

迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode a = queue.poll();
            TreeNode b = queue.poll();
            if(a==null && b==null){
                continue;
            }
            if(a==null || b==null){
                return false;
            }
            if(a.val != b.val) {
                return false;
            }
            queue.offer(a.left);
            queue.offer(b.right);
            queue.offer(a.right);
            queue.offer(b.left);
        }
        return true;
    }
}
查看原文

赞 0 收藏 0 评论 0

zhfang 发布了文章 · 1月12日

剑指 Offer 65. 不用加减乘除做加法

class Solution {
    public int add(int a, int b) {
        while(b!=0) {
            int c = (a & b)<<1;
            int n = a ^ b;
            a = n;
            b = c;
        }
        return a;
    }
}
查看原文

赞 0 收藏 0 评论 0

zhfang 发布了文章 · 1月12日

剑指 Offer 56 - I. 数组中数字出现的次数

异或满足交换律,第一步异或,相同的数其实都抵消了,剩下两个不同的数。这两个数异或结果肯定有某一位为1,不然都是0的话就是相同数。找到这个位,不同的两个数一个在此位为0,另一个为1。按此位将所有数分成两组,分开后各自异或,相同的两个数异或肯定为0(而且分开的时候,两个数必为一组)。剩下的每组里就是我门要找的数

class Solution {
    public int[] singleNumbers(int[] nums) {
        //用于将所有的数异或起来
        int k = 0;
        
        for(int num: nums) {
            k ^= num;
        }
        
        //获得k中最低位的1
        int mask = 1;

        //mask = k & (-k) 这种方法也可以得到mask,具体原因百度 哈哈哈哈哈
        while((k & mask) == 0) {
            mask <<= 1;
        }
        
        int a = 0;
        int b = 0;
        
        for(int num: nums) {
            if((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        
        return new int[]{a, b};
    }
}

作者:eddieVim
链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jie-di-qi-jiang-jie-fen-zu-wei-yun-suan-by-eddievi/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 3 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 2 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2020-03-03
个人主页被 1.1k 人浏览