16 B+树数据结构与索引基本原理
DELETE IGNORE
INSERT IGNORE
UPDATE IGNORE
CREATE TABLE ... REPLACE
判断NULL值与非NULL值 <=>
select * from test where b<=>NULL;
select * from test where b<=>1;
Percona Toolkit工具
pt-online-schema-change
修改字符集
pt_online-schema-change --alter "convert character set utf8mb4" D=emp,t=employees --alter-foreign-keys-metho=rebuild_constraints
堆表
数据存放在数据里面,索引存放在索引里
堆就是无序数据的集合,索引就是将数据变得有序,在索引中键值有序,数据还是无序的。
堆表中,主键索引和普通索引一样的,叶子节点存放的是指向堆表中数据的指针(可以是一个页编号加偏移量),指向物理地址,没有回表的说法。
堆表中,主键和普通索引基本上没区别,和非空的唯一索引没区别。
myisam就是用的这个堆表的存储方式,oracle支持堆表,pg只支持堆表
索引组织表
对于主键的索引,页子节点存放了一整行所有数据,其他索引称为辅助索引(二级索引),它的页子节点只是存放了键值和主键值。
主键包含了一张表的所有数据,因为主键索引的页子节点中保存了每一行的完整记录,包括所有列。如果没有主键,MySQL会自动帮你加一个主键,但是对用户不可见。
innodb中数据存放在聚集索引中,换言之,按照主键的方式来组织数据的。
其他索引(唯一索引,普通索引)的页子节点存放该索引列的键值和主键值。
不管是什么索引非页子节点存放的就是键值和指针,不存数据,这个指针在innodb中是6个bit,键值就看数据大小了。
MySQL 索引采用B+树的数据结构进行存储.
真实的数据存在于叶子节点，即3、5、9、10、13、15、28、29、36、60、75、79、90、99.
非叶子节点不存储真实数据，只存储指引搜索方向的数据项（指针），如17、35并不真实存在于数据表中。
索引的数据结构
一个磁盘相当于一个数据页，B+树的查找过程如下：
比如要查找数据项29:
首先会把磁盘块1加载到内存中，此时发生一次IO，在内存中用二分法查找 确定29在17 和35之间，锁定磁盘块1的P2指针，内存处理时间相对比磁盘IO非常短，可以忽略不计。
然后通过磁盘块1中的P2指针指向的地址把磁盘块3加载到内存中，此时发生第二次IO，采用二分法确定29在26和30之间，锁定磁盘块3中的P2指针。
最后通过磁盘块3中P2 指针指向的地址把磁盘块8加载到内存中，此时发生第三次IO，采用二分法查找到29，查询结束，共进行三次IO。
真实情况是，3层的B+树可以表示上百万的数据，如果上百万的数据查询只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本是非常高的。
有两点需要注意：
1、索引字段要尽量的小
我们知道IO次数取决于B+树的高度h，假设当前数据表的数据为N，每个磁盘的数据项的数量是m，则有h=log(m+1)N,当数据量N一定的情况下，m越大，h越小。
而 m=磁盘块大小/数据项大小，磁盘块的大小也就是一个数据页的大小，是固定的。如果数据项占据的空间越小，磁盘块所能容纳的数据项也就越多，那么树的高度也就越低。这就是为什么每个数据项（索引字段）要尽量的小。
2、索引的最左匹配原则（即从左往右匹配）
如查找(name,age,sex) 先匹配 name，再匹配 age ，最后匹配 sex，如果 name 没有匹配上则无法确定下一步。如果age缺失，则下一步匹配sex。
每一个父节点元素都出现在子节点中，为子节点的最大值或者最小值。
跟节点的最大元素即整个B+树的最大元素，之后无论增加或者减少元素，始终保持最大元素在跟节点。
叶子节点包含所有的数据，从左至右由小到大形成有序链表。
B+树的特征：
有k个子树的中间节点包含有一个k元素（B树中是k-1个元素），每个元素不保存数据，所有的数据均保存在叶子节点上。
所有的叶子节点中包含了全部元素的信息及指向含这些元素记录的指针，且叶子节点本身以关键字的大小自小到大顺序连接。
所有的中间节点元素都同时存在与子节点中，在子节点元素中为最大值或者最小值。
B+树的优势：
单一节点存储更多的元素，使得查询的IO次数更少。
所有查询都要查找叶子节点，查询性能稳定。
所有叶子节点形成有序链表，便于范围查询。
