索引与算法

B+树索引

聚集索引 clustered index

聚集索引是按照表主键构造的一颗B+树，叶子节点(也称为数据节点)中存放完整的数据行
非叶子节点，存放的是键值及指向数据叶的偏移量(可以理解为指向叶子节点的指针)
聚集索引逻辑上连续
页通过双向链表连接，按照主键排序，页中的记录也是双向链表连接

辅助索引 secondary index

也称非聚集索引

辅助索引的叶子节点包含了该索引列的值和主键的值

锁

锁机制用于管理对共享资源的并发访问。
提供数据的完整性和一致性。

lock和latch

	lock 锁	latch 闩
对象	事务	线程
保护	数据库内容	内存数据结构
持续时间	整个事务过程	临界资源
模式	行锁、表锁、意向锁	读写锁、互斥量
死锁	通过waits-for graph、time out等机制进行死锁检测与处理	无死锁检测与处理。仅通过应用程序加锁的顺序来保证无死锁的情况发生
存在于	lock manager的哈希表中	每个数据结构的对象中

innodb中的锁

一致性非锁定读

是指innodb通过多版本控制的方式来读取当前时间数据库内行的数据。

读取的行正在执行update或delete，这时读取操作不会等待锁释放，而是去读取快照数据。通过undo段来实现。

提交读隔离级别下，读取最新的快照。

可重复读，读取事务开始前的快照。

一致性锁定读

select … for update，加X锁，其他事务不能再枷锁。(别的事务可以进行读取，和一致性非锁定读情况一样)

select … lock in share mode，加S锁。

锁的算法

行锁的三种算法

record lock 单个记录上的锁
gap lock 间隙锁，锁定一个范围，但不包含记录本身
next-key lock 记录锁+间隙锁，锁定记录和范围，为了解决幻读，phantom problem（第二次查询会得到第一次查询中不存在的行）

eg. 10，11，13，20

(-无穷，10] (10,11] (11,13] (13,20] (20,+无穷)

查询的列是唯一索引的情况下，next-key lock 会退化成record lock，以提高性能。

Eg. a 为主键，唯一。 P267 ~ 268

a. select * from t where a = 5 for update;

b. insert into t select 4;

此时b会话不会阻塞。

锁问题

脏读读到未提交数据
不可重复读本文里包括幻读
丢失更新

阻塞

一个事务中的锁等待另一个事务的锁释放它所占用的资源

阻塞确保事务可以正常地运行

死锁

指两个或两个以上的事务在执行过程中，因争夺锁资源而造成的一种互相等待的现象

wait-for graph，等待图，一种较为主动的死锁检测，图中存在回路则存在死锁。在每个事务请求锁发生等待时都会判断是否存在回路，一般来说回滚undo量最小的事务。采用深度优先的算法实现，1.2版本后由递归版本优化为非递归版本。

锁升级

指将当前锁的粒度将低。

eg. 把一个表的1000个行锁升级为页锁，或将页锁升级为表锁。

InnoDB存储引擎-索引与算法