葵花宝典上（葵花宝典上半卷）

索引 索引是帮助Mysql高效获取数据的排好序的数据结构

索引数据结构有二叉树、红黑树(二叉平均树)、Hash表、B-Tree

树的每个节点是由key-value组成  key是数据 value是索引所在行的文件地址
mysql底层并没有用二叉树存储索引数据
因为二叉树有些场景不合适 比如Col1列的数据是从1递增的情况用二叉树就不合适
实际上mysql底层用的是B+Tree

红黑树

红黑树弊端

数据量越大 高度越不可控 无法避免很多次io磁盘操作

每个节点存储很多个索引结构 横向越大 存储数据量相同的情况下 高度越小 这就是B-Tree

B-Tree

• 叶子节点指针为空
• 节点中的数据索引从左到右递增排列

B+Tree

• 非叶子节点不存储data 只存储索引（冗余处于中间位置的索引） 可以存放更多的索引
• 叶子节点包含所有的索引元素
• 叶子节点用指针连接 提高区间的访问性能
• 首尾相接双向指针 两个节点之间的指针维护了每个节点在磁盘中的文件地址（B树也满足从左到右依次递增 只是没有相互双向指针）
• hash不是拍好序的

B+Tree索引结构

磁盘数据的一小页可能放了不少索引
把每一页的第一个元素 作为非叶子节点来组织一棵树

这是一个小的二叉树
右边的子元素大于等于左边的父元素
左边的子元素小于右边的父元素
节点内部也是有大小关系 从左到右依次递增

每个节点实际上是1页数据 mysql默认分配16KB内存

16KB的磁盘页放慢大概可以存放多少个元素？

假设索引使用bigint类型 占8个字节
指针地址mysql底层分配6个字节
一个索引元素为14个字节 非叶子节点可以存放1170个索引

叶子节点中的data元素有可能是索引所在行的磁盘文件地址
也可能是列数据 这种情况占用磁盘空间较大 比如是1KB 
那么叶子节点空间可以存放16个元素

这棵树全部放满之后大概可以存放 1170*1170*16=2千多万

高点版本的mysql 根节点和非叶子节点一般都是常驻内存的 查询的时候不需要从磁盘加载

所以只需要一次的io交互切树高度很少 且树的高度较小

MyISAM索引实现

存储引擎是形容数据库表的

MyISAM索引文件和数据文件是分离的即非聚集索引(稀疏索引)

MyISAM表结构

表的数据和索引存储在安装目录data目录下
一个库一个文件夹

一张表有3个文件

frm存储表结构
MYD存储表数据
MYI存储表索引数据（主键索引、二级索引（即普通索引））
索引和数据分开存储

查找某一条数据先去MYI文件 从根节点开始定位
找到叶子节点目标索引对应的所在行文件地址
到MYD去获取对应地址下的文件数据

InnoDB索引实现

• 表数据本身就是按B+Tree组织的一个索引机构文件
• 聚集索引：叶子节点包含了完整的数据记录

InnoDB表

ibd文件存放的是索引+数据

叶子节点存储的不是索引所在行的磁盘文件地址 而是索引所在行的列数据

聚集索引（聚簇索引）就是包含了完整的数据记录 索引以及索引所在行的列数据都放在了一起

主键索引就是一个聚集索引

如果不建主键 mysql底层 从第一列数据找 如果这列数据每个值都是唯一的 就是作为组织表B+Tree去存储

如果都没有找到 会默默在后台建立一个隐藏列 rowid 用rowid来组织

如果主键索引是字符串 需要逐步比对而且要转换成ASCII编码
主键是整型占用空间少 效率高

索引除了B+Tree结构 还有一种是Hash数据结构

Hash索引结构

• 对索引的key进行一次hash计算就可以定位出数据存储的位置
• 很多时间hash索引比B+Tree索引效率更高
• 仅能满足"=" "IN"不支持范围查询 如果是范围查询 不支持使用这个索引 还得全表扫描
• 存在hash冲突问题
• hash就是一种闪电算法 md5、crc16/32都是hash算法 mysql底层有自己的hash散列算法

递增索引结构

如果不自增

自增导致节点分裂的概率非常之小;非自增导致节点之前已经满16K的 再次分裂和平衡操作 很耗性能

二级索引即非主键索引 普通索引、辅助索引

和主键索引区别 是 叶子节点存储的是主键

联合索引

索引最左前缀原则

Redis

• redis基于内存(内存比磁盘IO或网卡将近快了 10万倍)只存在单步的网卡io的消耗

如果redis前面加一个中间件比如nginx就会设计到网卡io 那么性能就会差很多

• redis计算是串行化的（无论哪个版本 计算一定是单线程 顶多io是多线程）

多个客户端请求访问redis
redis内部做计算是单线程的处理 串行化的 所以可以保证并发安全
io处理和执行计算处理是并行的

上图访问redis 调用decr 对数值做减法操作 这个方法可以应用到 限流场景
将session cookie ip保存到redis中进行计数 记录单位时间内只能有多少次请求 做限流

• 有本地方法

k-v存储 v有本地方法 计算向数据移动 而不需要全部取出来

memcache

• 也是key-value存储 但value只有字符串类型
• 没有本地方法 把所有数据对网卡io都输出 需要在客户端json反序列化 做计算

如果是redis的话

没一数据类型都有一组本地方法

redis-cli
help @string

redis底层数据结构是二进制

raw是原生的字节数组

客户端编码设置为utf-8 中文字符占3个字节

客户端编码设置为gbk 中文字符占2个字节

如果此时将客户端编码格式变化 再次查询字节长度是不会变的
strlen 返回是字节数组的宽度
为了保证二进制安全 （无论是redis、kafka、zk、hbase） 必须把数据转字节数组交给客户端去存
redis服务端没有编码的概念 客户端之间要协商好

既然value是字节数组 那么客户端就可以将小文件转换成字节数组保存到redis
场景：几k或几百k的小文件 频繁被变更 （比如图片识别再做变更等）放在redis中是比较合适的

bigmap

k1对应的value是一个bigmap 二维矩阵 第二个参数1表示从左向右数的偏移量 第三个参数1表示 设置为1
该命令保存了1个字节的数据
一个字节等于8个二进制位

扩充10万个字节

1024字节为1K
12K存了1万多个字节

统计bigmap中二进制位中1的个数

BITCOUNT key 0 -1

开始位置是0 表示字节的下标 每个字节有8个二进制位


下标分为正负下标 从左向右分0...10

从右向左就是-1 -2...

-1 就是整个的所有字节

BITCOUNT key 0 0 表示统计第一个字节二进制位中1的个数

二进制位运算

BITOP add andkey key1 key2

add为位与运算
andkey表示2个key做位运算结果

表示2个key做二进制位运算

位与运算 全1则1 有0则0

BITOP or orkey key1 key2

or为异或运算

异或 有1为1 全0为0

二进制操作的使用场景：任意时间窗口内 统计登录的用户数 保存数据细节

统计一个人任意时间窗口内登录次数

这个用户一年中登录了3次

布隆过滤器

单向线性bigmap
redis做不隆过滤器 db中有的 才访问 没有 不访问

redis扩展模块 布隆过滤器 C语言开发的插件
本质是一个bitmap 一个key value是字节数组 每一个字节是8个二进制位
数据库中有ABC数据 将这些数据映射到bigmap里面
比如有3次hash函数计算 每次hash计算都会映射到数组中的某一个位置 标记1
3次就会有3个下标位置 即数据A对应到字节数组中有3个点

其他数据依次类推

查询数据D 3个hash计算对应到数组中的3个点是否全是1 
如果全是1 也不代表数据库中一定存在 如果不全为1 则数据库中一定不会存在数据D

12306基于二进制的bitmap来反映车站座位是否有票

未开售票的状态

行代表座位 a、b、c
列代表车站X、Y、Z
1代表本站该座位无票
空代表有票

车票未开始售票的时候 全都是0
每个车站和每个座位分别位与或异步运算结果都是0

已经购买过的票 状态为1

表示 XYZ三站a座位票已卖出

此时来了一个人购买票 ：想买ZWQ3站 可以买的票有哪些？abc都可以买

做位与运算 即可知道座位有没有票
前端页面可以绘制出来一张图片

redis sorted set 数据结构

底层数据结构实现是跳跃表

第一层是全量数据
第二层是从第一层中获取数据
第三层是从第二层中获取数据
性能堪比红黑树 实现更简单

粘包和拆包

 沾包的两种形式
 
 1、2个消息比较小 tcp传给服务端 服务端从缓存池中读取这2个消息作为一个消息
 2、2个消息 tcp传 m+部分n消息和剩下的n消息 发送给服务端 
 
 拆包：
 m消息比较大 发送2次才发送完 服务端作为2个数据包处理
 
 netty解决方法：
 
 消息定长处理 消息比较小 添加空格符 直到定长值
 消息末尾添加特殊分隔符 适合json字符串发送
 消息添加长度字段 适用范围较广

Synchronized

1、修饰方法
2、修改方法中代码块

ReentrantLock

锁模式

AQS

- 为什么需要AQS

  1、 锁类型分为：
  
     a、互斥锁（独占锁）：同时只有一个线程可以获得锁 （ReentrantLock）
     b、共享锁：允许多个线程同时拿到锁（例如：读写锁 ReadWriteLock 写锁和写锁、写锁和读锁互斥、读锁可以共享）
     
     这两个类都涉及到线程互斥问题 这就意味着总会有线程拿不到锁 那么这是为了避免CPU资源的浪费（一直执行无关的CAS） 所以我们需要将线程阻塞，既然涉及到线程的阻塞操作，那么必然会有唤醒操作，所以我们需要：
     
     a、存放等待线程的数据结构：队列
     b、操作线程阻塞和唤醒的方法：LockSupport类
     c、表示当前锁的状态 state变量 0无锁 1有锁
     所以AQS的出现就是对于互斥锁、共享锁的抽象：队列+state

- 什么是公平锁？什么是非公平锁

  1、公平锁：FIFO(先进先出) 根据AQS排队的队列来看 是否有线程在排队 如果没有则抢锁 如果有排队
  
  2、非公平锁：直接抢 管他有没有线程在排队

- 什么是抢锁

  AQS的实现有一个state变量 将其争夺修改为1 那么这种争夺行为叫做抢锁

- 怎么抢锁 抢锁的实现方式是什么

  CSA

AQS同步队列

CAS

HashMap实现原理

2个二进制做&位运算 同1为1 有0则0 所以低4位决定了下标值

hash值计算过程

向右无符号位移16位 再做异或运算
让高位的数据参与低位的计算

为什么要做异或运算

异或结果0/1概率一样 所以在数组中的分布足够分散

hashmap初始化时机

实例化HashMap的时候并没有初始化
而是在往里面存放元素的时候才会初始化
站在性能优化的角度或者程序编程角度 这样更节省内存

链表转红黑树

扩容2次 链表长度到达8 才会转换成红黑树

元素填满75%就会扩容
形成2个长度的链表只有7%

所以
绝大部分元素 要么链表为空 要么链表只有一个节点
几乎不会转换成红黑树

HashMap DOC漏洞攻击

key不同 hash一样 数据下标一样
可以造很长的链表 比如5万

http请求元素过多 导致tomcat解析时间过长 从而响应时间过长

1.7采用头插法插入链表元素

单线程没有问题 多线程情况下 会出现循环链表

一个线程已经扩容完成 另外一个线程还是获取到的之前的 再次进行扩容 容易形成循环链表

1.8采用尾插法

元素不会变化位置 出现死循环几率小
树很难形成死循环链表 

1.8加入红黑树

没有选择适用平均二叉树是因为平衡的代价比较高
红黑树 一定平衡 综合效率最高
红黑树的加入主要是为了解决性能问题 并不能避免链表的死循环

并发安全器

• hashtable 全表锁

• jdk1.7 ConcurrentHashMap 分段锁 默认创建16个分段

• jdk1.8

通过cas保存数组元素

通过syncronized加锁做链表处理

1.8 syncronized 本身就进行了优化 从偏向锁、cas、重量级锁 锁切换

ConcurrentHashMap 弱一致性

弱一致性 最常用的是读写一致
线程A写入元素 链表转换成红黑树 B立马就读到null 过段时间就可以读到

弱一致性的并发容器还有一个就是CopyOnWriteArrayList 写时复制

应用场景 电商查询黑名单 
将用户IP和用户ID添加黑名单中 保存在CopyOnWriteArrayList并发容器中
在下单的时候会判断当前用户是否是黑名单用户
凌晨2点 通过定时任务统计分析用户行为如果是异常用户则加入黑名单
弱一致性 多线程安全

并发读的时候不加锁
写的时候并不会影响原有数据的读
写完之后将原容器的引用指向副本

java方法运行与虚拟机栈

每个方法在运行的时候 会创建一个虚拟机栈

GC Roots主要包括四种

程序计算法（引用技术法） 没有办法处理相互引用问题
还需要额外机制 python就使用这种方式进行垃圾回收
java不是通过这种方式进行垃圾回收 而是通过可达性分析（根可达算法）
java的垃圾回收效率较高

分析Long l=1200L

字节码查看插件

long值在-128到127之间 包含2端 则会缓存Long对象  那么就有2个对象符合垃圾回收条件
所以正确答案是2/4个

复制算法

• 实现简单 运行高效
• 没有内存碎片
• 利用率只有一半

标记清除算法

标记整理算法

堆与垃圾回收

jvm在垃圾回收的时候会扫描Eden和其中一个S区

如果Eden区对象很大的话 就会提前晋级老年代 或者Eden区剩余内存假设还剩5M就直接晋级

这是appel式回收 空间利用率90% 只有10%的空间预留

1.8常见的垃圾回收器

新生代只有Serial和ParNew有大对象直接晋级的策略

这个参数可以控制大于多少M的对象可以直接晋级老年代

吞吐量最大的组合是PS组合

Parallel Scavenge 和 Parallel Old

垃圾回收器工作示意图

垃圾回收线程和业务线程并发

CMS垃圾回收器

单独针对老年代的垃圾回收器

老年代空间90% 80% 就要清理了
要有空间预留给下一次清理
不能等到空间全部?了才做一次垃圾回收

Serial、Serial Old、ParNew、Parallel Scavenge 可以等到空间满了 才进行回收

初始标记:找根直连的对象
并发标记
重新编辑 
并发清除

耗时长的标记做成并发 和 业务线程同时跑
然后做一次短暂的暂停 标记并发标记的过程中 发生变动的对象
并发清理 和 业务线程同时跑

CMS问题

CPU敏感：cpu核数低 不建议用CMS 会导致吞吐量下降 比如4核CPU 有4个GC线程也有4个业务线程 CPU 上下文频繁切换造成响应时间过长
浮动垃圾：只有在并发清理的时候会产生浮动垃圾（内存碎片）

CMS在并发清理的时候要预留空间存放垃圾

只有CMS才是并发清除
Serial Old、Parallel Old、G1是并发整理

标记整理有对象移动 必然要STW

cms是第一款并发收集的垃圾回收器 但jdk678没有将之默认

CMS如果还剩100M 但是有内存碎片 分配不了对象 此时JVM会进行干预 使用Serial Old单线程标记整理 STW 会有很大的停顿

G1垃圾回收器

• 追求停顿时间
• Region区(化整为零 将整个内存划分一小块一小块的Region区 比如1G内存 分100块 每一块10M )

H区专门放大对象 没有动态年龄判断 直接晋级
G1逻辑上有这些区域 物理上是不连续的

如果某一个E区所有对象都可以进入老年代 直接标记为O区即可

• 筛选回收 STW

追求停顿时间 做了一次筛选回收

期望g1停顿时间100毫秒 比如有4个区域 是回收效率最高的 90%都是垃圾 则会优先回收这4个区域 已达到停顿时间100毫秒

筛选出来性价比最高的区域

• 可预测停顿

只是可预测 不是绝对

• 算法--复制和标记整理算法

跨越了新生代和老年代的

如果堆内存在6G以上 基本上用G1

有很多优化策略

新生代 复制
老年代标记整理 没有内存碎片

比较差的点是 如果内存比较少 比如200M 化100快 每一块2m 比较小

没有cms那么多问题