数据结构和算法 IV

数据结构和算法 IV

面试题

冒泡排序

• 排序算法

• 原理机制: 相邻元素两两比较,大的/小的往后排,一轮比较结束,最大值出现在最大下标处.会比较多轮
  

• 代码实现

  public static void main(String[] args) {
          int[] ary = {23,12,7,0,67,9,11};
  
          for (int i=0;i<ary.length-1;i++){  //i表示轮数
              for (int j=0;j<ary.length-1-i;j++) {  //j表示遍历元素的下标
                  if (ary[j]>ary[j+1]){
                      int tmp = ary[j];
                      ary[j]=ary[j+1];
                      ary[j+1] = tmp;
                  }
              }
          }
  
          System.out.println(Arrays.toString(ary));
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

• 练习

  1. 对int[] 升序排列
  2. 对int[] 降序排列
  1
  2

数据库

锁

• 锁的分类

  1. 按照锁的粒度分:表锁    行锁
  2. 锁的类型分:
  	共享锁:也叫做share锁/S锁
  		特点:可以给表加,也可以给行数据加,其特点为: 给目标数据加上share锁之后允许其他事务继续对该数据加share锁,不允许其他事务对该数据加排它锁;通常读取数据时使用
  				
  	排他锁/独占锁:也叫X锁
  		特点:给数据加排它锁,不允许其他事务继续给该数据加排它锁,同时不允许其他事务给该行数据加共享锁,适用于写操作
  		
  在数据库中,经常执行读写操作为:
  	select....
      insert...
      delete...
      update....
          
      增删改操作默认给操作的行数据加排它锁
      select操作默认不加任何锁
      
  如何在查询时加共享锁/排它锁
  	select ......lock in share mode;     //查询加共享锁
  	select.....for update;  //查询加排它锁	
  	
  select...from ..where like ''  --表锁
  
  mysql的存储引擎：
    mysql5.5开始存储引擎变成InnoDB，特点：支持行锁 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25

悲观锁和乐观锁

• 是两种思想

• 悲观锁:

  当多事务/多线程并发执行时,事务总是悲观的认为,在自己访问数据期间,其他事务一定会并发执行,此时会产生线程安全问题,所以为了保证线程安全,这个事务在访问数据时,立即给数据加锁,从而保证线程安全.
  特点:可以保证线程安全,但是并发执行效率低下
      
      synchronized   排它锁都是悲观锁的应用
  1
  2
  3
  4

• 乐观锁:

  在多线程/多事务并发执行中,某个事务总是乐观的认为,在自己执行期间,没有其他事务与之并发,认为不会产生线程安全问题,所以不会给数据加锁;但是确实存在其他事务与之并发执行的情况,确实存在线程安全问题,为了保证线程安全,通过版本号机制或CAS来保证线程安全.
      
  CAS:compare and swap  比较并交换
  1
  2
  3

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eWQwd6Pn-1663914819503)(版本号机制.png)]

事务

• 什么是事务

  事务是数据库中执行操作的最小执行单元，不可再分，要么全都执行成功，要么全都执行失败。
  1

• 事务的四大特性

  原子性   一致性   隔离性    持久性
  1

• 数据库中事务自动提交默认开启

  查看事务的自动提交是否开启：
  	show variables like 'autocommit'
  		on  off
  如何关闭事务自动提交：
  	set autocommit=off;
  
  事务管理：
  	开启事务： begin
  	提交事务： commit
  	回滚事务： rollback
  	
  对数据库的增删改操作默认开启事务，而select不涉及事务
  
  
  当业务方法涉及到多步增删改操作时，且想要他们保证要成功全成功，但凡有一个操作失败，则整个操作应该全部失败，此时就应该为这个业务方法开启事务管理。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

• 死锁

• • 数据库中出现死锁，数据库是如何解决的？

    clientA:
    	1. setautocommit=off
    	2. begin;
    	3. update student set sname=xx where sno=1
    	4. delete from course where cno=1
    	
    clientB:
    	1. setautocommit=off
    	2. begin;
    	3. update course set..where cno=1
    	4. delete from student where sno=1
    	
    mariadb对死锁的处理:检测到死锁后,让一端的事务回滚,并提示DeadLock,让另一端的事务执行成功.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13

视图 --View-- 笔试题 创建视图

• 什么是视图

  视图是虚拟表,用于展示结果集,其中并不保存数据,其数据来源于真实表中.视图实质上是用于封装sql的,后续若想再次执行相同的sql,直接调用视图名称即可.
      
  场景:
  	在数据库中若要多次展示同样的数据,其数据来源于4表,一样的sql写多次,此时出现了sql重复问题
  	数据库如何解决这个问题?
          将上述的sql封装起来,给这个sql起一个名字,后续若想再次执行改sql,直接调用名字即可
          
         create view view_name as select....from A join B join c join D .........    
  1
  2
  3
  4
  5
  6
  7
  8

• 操作视图

  创建视图
  	create view view_name as select.......
  	create view view_name(col1,col2,col3,col4) as select......
  
  调用视图 :因为视图是虚拟表,所以对视图的操作和对表的操作是一样的
  	select ...from  table_name
  	select ...from view_name
  	
  	desc table_name;
  	desc view_name;
  
  删除视图   
  	drop table table_name
  	drop view view_name
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

• 视图注意事项:

  1. 视图实质上是对sql的封装,而不是对结果集的封装,视图的存在并不是用于提高查询效率的,效率不会提高
  2. 视图的存在是用于查询的,而不是用于对数据进行写操作,所以不应该对视图执行update操作,但是数据库语法上允许对视图执行update操作,但是不一定成功.
      - 视图来源于单表
      	- 修改 -- 成功
      	- 删除 -- 成功
      	- 增加 -- 成功
      - 视图来源于多表
      	-- 修改
      		1. 修改一张表的字段 -- 成功
      		2. 同时修改2表的字段 -- 失败
      	-- 删除 -- 失败
      	-- 添加 -- 失败    
  3. 因为视图中并不保存数据,其数据来源于真实表中,所以真实表中的数据发生改变,视图中的数据一定会随之改变
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

事务隔离级别 – 面试必考

• 4种

  read uncommitted  读未提交  -- RU
  read committed   读已提交  -- RC
  repeatable read  可重复读  --RR
  serializable    可串行化  
  1
  2
  3
  4

• 读未提交

  特点:事务可以读取到其他事务未提交/未回滚前的数据,会产生脏读
  什么是脏读:由于事务读取到了其他事务未提交/未回滚前的数据,导致读取的数据最终是不存在的,这个现象就叫做脏读.
  1
  2

• 读已提交

  特点:事务只能读取到其他事务提交/回滚后的数据,解决了脏读问题,但是会产生不可重复读问题.
  
  什么是不可重复读:在事务A执行期间,其他事务对事务A访问的数据进行修改操作,导致事务A中前后两次读取相同的数据的结果是不一致的.这个现象就叫做不可重复读
  1
  2
  3

• 可重复读

  解决了不可重复读问题,产生了新的问题 -- 幻读
  什么是幻读: 在事务A访问数据期间,其他事务执行了插入操作,导致事务A前后两次读取到的数据总量不一致,这个现象就叫做幻读.
  1
  2

• 可串行化

  解决了幻读问题,实现了多事务并发执行同步效果,所以这个隔离级别的并发执行效率是最低下的
  1

• 四种隔离级别由低到高

  读未提交-->读已提交-->可重复读-->可串行化
  1

• 四种隔离级别可能产生的问题

  	脏读	不可重复读	幻读
  读未提交	√	√	√
  读已提交	×	√	√
  可重复读	×	×	√
  可串行化	×	×	×

• 数据库默认的隔离级别

  oracle和sql server 默认的隔离级别为 读已提交
  mysql的 默认隔离级别为 -- 可重复读
  1
  2

• mysql默认的隔离级别可重复读是如何实现的?

  存储引擎为Innodb的mysql,其隔离级别可重复读的实现是通过MVCC实现的
  1

• MVCC（Multi-Version Concurrency Control）- 多版本并发控制

  多版本并发控制解决了并发安全问题,且并发执行效率高很多.
      
  MVCC的实现由三部分配合实现:
  	1. undolog  
  	2. mysql中的表里边每个表都有隐藏的三个字段
  	3. ReadView
  1
  2
  3
  4
  5
  6

• 隐藏字段

  row_id -- Innodb存储引擎提供的隐藏主键 -- 当表中没有主键时自动生成 -- 隐藏主键
  DB_trx_id   -- 事务的id  --  该列中保存的id值为最后操作该数据的事务id
  DB_roll_ptr  -- 数据回滚指针,保存要回滚到的数据的地址
  1
  2
  3

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TYQVnGtz-1663914957926)(隐藏字段.png)]
  

• ReadView

  事务执行操作时,会生成当前事务的ReadView,ReadView保存当前事务之前活跃的所有事务id
  
  ReadView有四个字段:
  m_ids: 截止到当前事务id之前,所有活跃的事务id
  min_trx_id: 记录以上活跃事务id中的最小值
  max_trx_id: 保存当前事务结束后应分配的下一个id值
  creator_trx_id: 保存创建ReadView的当前事务id
  1
  2
  3
  4
  5
  6
  7

• 三者如何配合实现mysql的隔离级别

我是将军；我一直都在，。！