平衡多路查找树 B-Tree
B + Tree
B+ 树是B树的变体,其定义基本与B树相同,除了:
B+Tree更适合用来做存储索引
Hash索引:
hash索引的查询效率是很高的,hash索引是通过has函数运算后,只需要经过一次定位,就可以找到查询数据的头,不像B树要从根节点到非叶子节点再到叶子节点,最后才能访问到我们要查询的数据,这样就会进行多次I/O访问
缺点:
位图索引 ---------- 仅有Oracle支持
密集索引文件中的每个搜索码值都对应一个索引值------- 即叶子节点不仅保存了键值,还保存了位于同一条记录的其他列信息,由于密集索引决定了表的物理排列顺序,一个表只能创建一个密集索引
稀疏索引文件只为索引码的某些键建立索引项------- 即叶子节点只保存了键位信息以及索引主键
MySQL主要有两种存储引擎:
InnoDB ------------ 索引和数据是存在一块的
MYISAM ----------- 索引和数据是分开的
为什么要使用索引? 因为索引能让我们避免全表扫描去查找数据,提升检索效率
什么样的信息能成为索引? 主键,唯一键等,只要是能让数据具备一定区分性的字段,都能成为索引
索引的数据结构? 主流是B+树,还有Hash结构
根据慢日志定位慢查询sql
使用explain等工具分析sql
修改sql或者尽量让sql走索引
mysql有很多系统变量,查询和慢日志相关的配置信息,慢日志就是用来记录执行比较慢的sql
show variables like '%quer%'
-------- 关注慢日志,打开慢日志,查看慢日志时间
show status like '%slow_queries%'
---------- 慢查询sql的数量
set global slow_query_log = on
----------- 打开慢日志,这个是临时改变的,重启数据库又会到默认值
set global long_query_time = 1
------- 设置慢查询的时间为1s
关键字type字段:index,all就代表实在全表扫描了,需要进行sql优化
extra
最左匹配原则:非常重要的原则,mysql会一直向右匹配直到范围查询(<,>,between,like)就停止匹配,比如a=3,b=4, and c>5 and d=6 ,建立(a,b,c,d)顺序的索引,d是用不到索引的,如果建立(a,b,d,c)的索引则可以用到
索引建立的越多越好吗?
MyISAM默认用的是表级锁,不支持行级锁
InnoDB默认用的是行级锁,也支持表级锁
读锁 ------ 共享锁 lock tables 表名 read
对表加上读锁时,在进行范围查询时,其他人仍然可以对数据进行查询 写锁-------- 排它锁
需要等待写锁的释放,才能执行其他语句
当不走索引时,就会使用表级锁,若SQL用到了索引,就会使用行级锁
MYISAM使用的场景:
InnoDB使用的场景
数据库锁的分类
select @@tx_isolation
查看事务的隔离级别
set session transaction isolation level read uncommited
设置当前会话窗口的事务隔离级别为 读未提交,该方式会发生脏读,即允许读到其他事务未提交的数据
start transction;
开启手动事务
**事务并发访问引起的问题以及如何避免?**考察事物的隔离级别
InnoDB可重复读隔离级别下,如何避免幻读?
表象:快照度(非堵塞读)— 伪MVCC(多版本并发控制)
当前读:select .... lock in share mode select .... for update, insert update delete
快照读:不加锁的非阻塞读,在可重复读级别下可能读取到之前版本的数据,取决于快照的时间
RC,RR级别下的InnoDB的非阻塞读(快照度)如何实现? 1.数据行里的DB_TRX_ID(事务id),DB_ ROLL_PTR(回滚指针),DB_ROW_ID(行号)字段
2.undo日志 日志的工作方式:这里以更新为例
在修改前,先将数据拷贝一份到Undo log中
数据的各个版本就是这样实现的,按照修改的时间,从近代远,按照DB_ROLL_PTR
连接起来
3.read view 做可见性判断,根据可见性算法,显示可以看见的数据版本
内在:next-key锁(行锁+gap锁)
对主键索引或者唯一索引会用Gap锁吗?
调用start()方法会创建一个新的子线程并启动
run()方法只是Thread的一个普通方法的调用
Thread是实现了Runnable接口的类,使得run支持多线程
因类的单一继承原则,推荐多使用Runnable接口
主线程等待法------------- 让主线程循环等待,需要自己实现循环等待的逻辑,无法控制循环的时间
使用Thread类的join()阻塞当前线程以等待子线程处理完毕 -------- 无法可控制粒度更细的依赖关系
通过Callable接口,通过FutureTask 或者 线程池获取
实现Callable接口,重写含有返回值的Call方法,FutureTask的构造函数中需要一个Callable接口实现类的对象,futureTask是间接继承Runable接口的,所以可以将FutureTask对象传入到Thread构造函数中
在Thread源码中,有一个State的枚举类型,该枚举类型中有6个值 从源码和官方说明中,线程有6个状态
基本差别:
本质区别:
锁池:假设线程A已经拥有了某个对象锁,而其他线程B,C想要调用这个对象的某个synchronized方法或者代码块之前必须获得该对象的锁,而恰巧该对象的锁正被A线程占用,此时B,C线程就会被阻塞,进入一个地方去等待锁的释放,这个地方就是该对象的锁池
等待池:假设线程A调用了某个对象的wait()方法,线程A就会释放该对象的锁,同时线程A就进入了该对象的等待池中,进入的等待池的线程不会去竞争该对象的锁
notifyAll会让所有处于等待池中的线程,全部进入锁池去竞争获取锁的机会
notify只会随机选取一个处于等待池中得线程,进入锁池中去竞争获取锁的机会
yield:当调用Thread,yield()方法时,会给线程调度器一个当前线程愿意让出CPU使用的暗示,但是线程调度器可能会忽视这个暗示
已被抛弃的方法:通过调用stop()方法停止线程 -------- 可以由一个线程调用stop方法,终止另一个线程,该方法太过暴力,而且是不安全的
线程A调用线程B的stop方法,去停止线程B,但线程A其实并不知道线程B的具体执行情况,这种突然的停止动作会导致线程B的一些清理工作无法完成,还有就是执行stop方法后,线程B会马上释放自己的锁,这样有可能会引发数据不同步的问题
目前使用的方法:调用interrupt()
方法,通知线程应该中断了
因此Interrupt并不能真正是线程中断,需要被调用的线程配合中断
线程状态以各个状态之间的转换:
实现synchronized的基础
自旋锁与自适应自旋锁 许多情况下,共享锁的锁定状态持续时间较短,切换线程不值得,通过让线程执行忙循环等待锁的释放,不让出CPU;若锁被其他线程很长时间占用,会带来许多性能上的开销
自适应自旋锁:自旋的次数不在固定,由前一次在同一个锁上的自旋时间及锁的拥有者状态来定
锁消除:JVM对锁另一种更彻底的优化,JVM在JIT编译时,对运行上下文进行扫描,去除不可能存在竞争的锁。
锁粗化:另一种极端:通过扩大锁的范围,避免反复加锁和解锁
synchronized的四种状态 无锁 —> 偏向锁—> 轻量级锁 —>重量级锁
偏向锁:减少获取同一锁的代价 CAS(Compare And Swap)
大多数情况下,锁不存在多线程竞争,总是由一个线程多次获得
核心思想:如果一个线程获得了锁,那么锁就进入偏向模式,此时Mark Word的结构也变为偏向所的结构,当该线程再次请求锁时,无需再做任何同步操作,及获取锁的过程只需要检查Mark Word的锁标记位为偏向锁以及当前线程Id等于Mark Word的ThreadId即可,这样就省去了大量有关锁申请的操作
不适用于锁竞争比较激烈的多线程场合
轻量级锁:轻量级锁是由偏向锁升级来的,偏向锁运行在一个线程进入同步快的情况下,而第二个线程加入锁争用的时候,偏向锁就会升级位
轻量级锁:适应的场景:线程交替执行同步快 若存在同一时间访问同一锁的情况,就会导致轻量级锁升级到重量锁
ReentranLock公平性的设置
ReentanLock faireLock = new ReentanLock(true)
参数为true时,倾向于将锁赋予等待时间最长的线程
公平锁:获取锁的先后顺序按先后调用Lock()方法的顺序
非公平锁:抢占顺序不一定,看运气
synchronized是非公平锁
总结
机制:sync操作Mark Work,lock调用Unsafe类的park()方法
指令重排需要满足的条件:
CAS(Compare And Swap):一种高效实现线程安全性的方法 支持原子更新操作,适用于计数器,序列发生器等操作
属于乐观锁机制,号称lock-free
CAS操作失败时由开发者决定是继续尝试,还是执行别的操作
CAS多数情况下对开发者来说是透明的
J.U.C的atomic包提供了常用的原子性数据类型以及引用,数组等相关原子类型的更新操作工具,是很多线程安全的首选
Unsafe类虽然提供CAS服务,但因为能够操作任意内存地址读写而又隐患
缺点:若循环时间长,则开销很大,只能保证一个共享变量的原子操作,ABA问题
在web开发中,服务器需要接收并处理请求,所以会为一个请求来分配一个线程来进行处理,如果并发的请求数量比较多,但每个线程执行的时间很短,这样就会频繁的创建和销毁线程,这样一来就会大大降低系统的效率,可能出现服务器在为每个线程创建和销毁的时间比实际处理请求消耗的时间更多
利用Excutors创建不同的线程池满足不同场景的需求
newFixedThreadPool(int nThreads)
------ 指定工作线程数量的线程池newCachedThreadPool()
-------- 处理大量短时间工作任务的线程池 newSingleThreadScheduledExcutor()
与 newScheduledThreadPool(int corePoolSize)
定时或者周期的工作调度,两者的区别在于单一工作线程还是多个线程newSingleThreadEcecutor()
创建唯一的工作者线程来执行任务,如果线程异常结束,会有另一个线程取代为什么要使用线程池 降低资源消耗 提高线程的可管理性
J.U.C的三个Excutor接口
Excutor
:运行新任务的简单接口,将任务提交和任务执行细节解耦
ExcutorService
:具备管理执行器和任务生命周期的方法,提交任务机制更完善
ScheduledExcutorService
:支持Future的定期执行任务
TreadPoolExcutor的工作模式如图:
ThreadPoolExcutor的构造函数:
corePoolSize
:核心线程数量maximumPoolSize
:线程不够用时能够创建 的最大线程数workQueue
:任务等待队列keepAliveTime
:抢占的顺序不一定,看运气threadFactory
:创建新线程,Excutors.defaultThreadFactory()
,优先级不变,也设置了线程名称handler
:线程池的饱和策略 AbortPolicy
:直接抛出异常,默认策CallerRunsPolicy
:用调用者所在的线程来执行任务DiscardOldsPolicy
:丢弃队列中最靠前的任务,并执行当前任务DiscardPolicy
:直接丢弃任务RejectExcutorHandler
接口的自定义handler
新任务提交excutor
执行后的判断:
corePoolSize
,则创建新线程来处理任务,即使线程池中的其他线程是空闲的;corePoolSize
且小于maximumPoolSize
,则只有当workQueue
满时,才创建新的线程去处理任务corePoolSize
和maximumPoolSize
相同,则创建的线程池大小是固定得,这时如果有新任务提交,若workQueue
未满,则将请求放入workQueue
中,等待有空闲的线程去从workQueue
中去取任务并处理;maximumPoolSize
,这时如果workQueue
已经满了,则通过handler
所指定的策略来处理任务线程池的状态
Running
:能接收新提交的任务,并且也能处理阻塞队列中的任务shutdown
:不再接收新提交的任务,但可以处理存量任务stop
:不再接收新提交的任务,也不处理存量任务Tidying
:所有 的任务都已终止TERMINATED
:terminated()方法执行后进入该状态CPU密集型:线程数 = 按照核数或者核数+1设定
I/O密集型:线程数 = CPU数 * (1+平均等待时间/平均工作时间 )
Error:程序无法处理的系统错误,编译器不做任何检查
Exception:程序可以处理的异常,捕获后可能恢复
总结:前者是程序无法处理的错误,后者是程序可以处理的异常
具体明确:抛出的的异常应该能通过异常类名和message准确说明异常的类型和产生异常的原因;
提早抛出:应尽可能早的发现并抛出异常,便于精确定位问题;
延迟捕获:异常的捕获和处理应尽可能延迟,让掌握更多信息的作用域来处理异常
在用户看来,应用系统发生的所有异常都是应用系统内部的异常
设计一个通用的继承自RuntimeException的异常来统一处理,设为AppException
其余异常都统一转义为上述异常AppException
在catch之后,抛出上述异常的子类,并提供足以定位的信息 由前端接收AppException做统一处理
try-catch代码块影响JVM的优化
异常对象实列需要保存堆栈快照等信息,开销较大
HashMap(Java8以前):数组+链表
Java8及以后:数组+链表+红黑树:当链表的长度大于8时,就会转为红黑树
HashMap:put方法的逻辑
HashMap:如何有效减少碰撞
如何优化Hashtable? 通过锁细粒度化,将整锁拆解成多个锁进行优化
ConcurrentHashMap:put方法的逻辑
三者的区别?
java,util.concrrent
:提供了并发编程的解决方案
java,util,concrrent.atomic
包的基础java,util,concrrent.locks
包及一些常用类,比如Semophore,ReentranLock等类的基础J.U.C包的分类
Block-IO:inputStream和OutputStream,Reader和Writer
NonBlock-IO:构建多路复用,同步非阻塞的IO操作
NIO的核心
Asynchronous IO:基于事件和回调机制
AIO如何进一步加工处理结果
CompletionHandler
接口,调用时触发回调函数isDone()
查看是否准备好,通过get()
等待返回数据