第四章、表

　　4.1、innodb存储引擎表类型

　　innodb表类似oracle的IOT表(索引聚集表-indexorganized table)，在innodb表中每张表都会有一个主键，如果在创建表时没有显示的定义主键则innodb如按照如下方式选择或者创建主键。

　　首先表中是否有唯一非空索引(unique not null)，如果有则该列即为主键。

　　不符合上述条件，innodb存储引擎会自动创建一个6字节大小的指针，rowid().

　　4.2、innodb逻辑存储结构

　　innodb的逻辑存储单元由大到小分别是 tablespace,segment,extent,page(block)组成。

　　4.2.1、表空间(tablespace)

　　大部分内容和3.6.1章节相同，可以通过产生undo操作来验证共享表空间存储undo的信息，也可以通过py_innodb_page_info.py来查看表空间文件中各页的类型和数量。

　　4.2.2、段(segment)

　　常见的segment有数据段、索引段、回滚段。

　　由于我们刚才说过，innodb是索引聚集表，所以数据就是索引，索引就是数据，那么数据段即是B+树的页节点(leaf node segment),索引段即为B+树的非索引节点(non-leaf node segment).innodb的segment是innodb自动完成的，不许要人工参与。

　　4.2.3、区(extend)

　　区是由64个连续的页主成，每个页大小为16K，即每个区的大小为(64*16K)=1MB,对于大的数据段，mysql每次最多可以申请4个区，以此保证数据的顺序性能。

　　对于innodb_file_per_table参数的特殊情况，开启这个参数后，默认创建的表空间大小为96K。 区是64个连续的页，应该创建1M才对啊?原因就是每个段开始时有32个页大小的碎片页(fragment page)来存放数据，当这些页使用完成以后，才是32+64个连续页的申请。具体参见P75的实验。

　　4.2.4、页(page)

　　页是innodb磁盘管理最小的单位，innodb每个页的大小是16K。常见的页类型有：

　　数据页 B-tree Node

　　undo页 Undo Log Page

　　系统页 System Page

　　事务数据页 Transaction system Page

　　插入缓冲位图页 Insert Buffer Bitmap

　　插入缓冲空闲列表页 Insert Buffer free Bitmap

　　未压缩的二进制大对象页 Uncompressed BLOB Page

　　压缩的二进制大对象页 Compressed BLOB Page

　　4.2.5、行

　　innodb存储引擎是面向行的(row-oriented),也就是说数据的存放按行进行存放。每个页最多可以存放16K/2～200行,也就是8192和81.92个行。

　　也有面向列的数据库(column-orientied), mysql infobright就是面向列的，对于数据仓库下的分析类sql语句和数据压缩很有好处。

　　4.3、innodb物理存储结构

　　innodb引擎由共享表空间，日志文件(redo log)，表结构定义文件组成。如果开启了innodb_file_per_table，那每个表将独立的产生一个表空间文件，以ibd结尾，数据、索引、表的内部数据字典都将被保存在这个单独的表空间中。

　　4.4、innodb行记录格式

　　mysql从5.1开始，innodb提供了compact和redundant(为了兼容以前版本)两种格式来存放行记录数据。可以通过show table status like tG来查看格式。

　　4.4.1、compact行记录格式

　　P85

　　4.4.2、redundant行记录格式

　　P88

　　4.4.3、行溢出数据

　　varchar(N)最多可以存储多少个字符跟表的字符集格式有关系，在latin1下，varchar可以存储65532个字符，在GBK下可以存储32767个字符，和UTF8下可以存储21845个字符。使用?varchar 提示的0-65535指的是字节。

　　一个页是16K，如何存储65535字节呢?这个时候就会出现行溢出，在B-tree节点页存储768字节的前缀，剩下的数据存入Uncompressed BLOG Page。为什么会在B-tree节点页存储768个字节，而不全部存进去呢?因为innodb是索引组织表(B-tree)，一个页中至少应该有2条记录，否则就成链表，失去了B+树的意义。所以innodb会自我优化，一个页中如果只能存放一条记录，那么innodb存储引擎会自动将数据存储到溢出页。

　　4.4.4、compressed与dynamic记录格式

　　P98

　　4.4.5、char的行结构存储

　　从mysql4.1开始CHR(n)，中N指定的是字符的长度，而不是之前版本的字节长度。也就是说在不同字符集下，CHAR的内部存储不是定长的数据。可以通过select a,char_length(a),length(a) from t;查看字符和字节数。所以在多字符集下，char和varchar占用a空间是一样的。

　　4.5、innodb数据页结构

　　P101

　　4.6、named file formats

　　innodb存储引擎通过named file formats机制来解决不同版本下页结构兼容性问题。

　　4.7、约束

　　4.7.1、数据完成行

　　innodb提供了以下四种约束

　　Primary key

　　Unique Key

　　Foreign Key

　　Default

　　Not NULL

　　4.7.2、约束的创建和查找

　　创建时候定义，或者使用alter table定义。

　　4.7.3、约束和索引的区别

　　primary key和unique key既是约束也是主键。约束是一个逻辑的概念，用来保证数据完整性，而索引是一个数据结构，有逻辑上的概念，在数据库中更是一个物理存储的方式。

　　4.7.4、对于错误数据的约束

　　可以通过修改sql_mode来保证约束的强制性。

　　4.7.5、ENUM和SET约束

　　由于mysql不支持check约束，所以可以通过ENUM和SET来实现部分需求，还可以通过触发器来实现check约束，注意需要修改sql_mode=’strict_trans_tables’;

　　4.7.6、触发器

　　P121

　　4.7.7、外键

　　P123

　　4.8、视图

　　4.9、分区表

　　4.9.1、分区表的概述

　　分区表不是在存储引擎曾完成的，所以不止innodb支持分区表功能。myisma，ndb等都支持，csv、federated、merge等不支持。

　　mysql的分区表是水平分区，并不是垂直分区，mysql的分区表是局部分区索引，一个分区中既存储数据又存放索引。

　　可以通过 show variables like ‘%partition%’;查看mysql是否支持分区表功能。

　　当前mysql数据库支持以下几种类型的分区：

　　Range分区 行数据基于属于一个给定连续区间的列值放入分区，这个值只能是整数。

　　RANGE CLUMNS分区 5.5开始支持

　　LIST分区 和range类似，只是list分区里面是离散的值，这个值只能是整数

　　LIST CLUMNS分区 5.5开始支持

　　HASH分区 根据用户自定义的表达式的返回值进行分区，返回值不能是负数。

　　KEY分区 根据mysql数据库提供的哈西函数进行分区

　　不论什么类型的分区，如果表中存在主键和唯一索引，那么分区列必须是主键或者唯一索引的一个组成部分。否则回报错。

　　4.9.2、range分区

create table t_range( 　　id int(11), 　　money int(11) unsigned not null, 　　date datetime 　　)partition by range(year(date))( 　　partition p2007 values less than (2008), 　　partition p2008 values less than (2009), 　　partition p2009 values less than (2010) 　　partition p2010 values less than maxvalue 　　)

　　可以使用 select * from INFORMATION_SCHEMA.partitions where table_schema=database() and table_name=’t_range’G查看分区的相关信息。

　　可以使用 explain partitions select * from t_range where date > ’2010-10-10′;来分析分区使用的索引和执行情况。

　　对range分区的查询，优化器只能对YEAR(),TO_DAYS(),TO_SECONDS(),UNIX_TIMESTAMP()这类函数进行优化选择，所以在规划partition by range时的分区函数一定要用上面的类型才能达到优化的目的。

　　4.9.3、list分区

create table t_list( 　　a int(11), 　　b int(11) 　　)(partition by list (b) 　　partition p0 values in (1,3,5,7,9), 　　partition p1 values in (2,4,6,8,0) 　　);

　　对于innodb和myisam引擎，一条语句插入多条记录的时候，如果中间有值不能插入，innodb会全部回滚，myisam在错误值之前的数据可以插入到表中。

　　4.9.5、hash分区

　　hash分区的目的是将数据均匀的分布到预先定义的各个分区中，保证各分区的数据量大致一致。

create table t_hash( 　　a int(11), 　　b datetime 　　)partition by hash (YEAR(b) 　　partitions 4;

　　hash的分区函数页需要返回一个整数值。partitions子句中的值是一个非负整数，不加的partitions子句的话，默认为分区数为1。

　　4.9.6、key分区

　　key分区和hash分区相似，不同在于hash分区是用户自定义函数进行分区，key分区使用mysql数据库提供的函数进行分区，NDB cluster使用MD5函数来分区，对于其他存储引擎mysql使用内部的hash函数，这些函数基于password()一样的算法。

create table t_key( 　　a int(11), 　　b datetime) 　　partition by key (b) 　　partitions 4;

　　4.9.6、columns分区

　　上面介绍的RANGE、LIST、HASH、KEY四种分区中，分区的条件必须是整形，如果不是整形需要通过函数将其转换为整形。

　　mysql-5.5开始支持COLUMNS分区，可视为RANGE和LIST分区的进化，COLUMNS分区可以直接使用非整形数据进行分区。COLUMNS分区支持以下数据类型：

　　所有整形，如INT SMALLINT TINYINT BIGINT。FLOAT和DECIMAL则不支持。

　　日期类型，如DATE和DATETIME。其余日期类型不支持。

　　字符串类型，如CHAR、VARCHAR、BINARY和VARBINARY。BLOB和TEXT类型不支持。

　　COLUMNS可以使用多个列进行分区。

　　4.9.7、子分区

　　mysql允许在RANGE和LIST分区上再进行HASH或者key的子分区。

　　每个分区上的子分区数量必须相同。

　　在每个分区内，子分区的名称是唯一的，

　　分区可以放到不同磁盘上。

　　4.9.8、分区中的NULL值

　　RANGE,HASH,KEY分区如果插入null值，mysql会把它放入最左边的分区，如果删除最左边的分区，null值不会被删除，他会记录到新的最左边的分区。

　　LIST分区如果没有指定NULL值的存放位置，那么就会报错。

　　4.9.9、分区的性能

　　OLTP系统不适合使用分区表，如果磁盘空间和磁盘IO没出现瓶颈，也不建议使用分区表。

　　第五章、索引与算法

　　索引和开销是需要找一个平衡点，过多或者过少都会影响性能，从而导致负载过高，浪费硬件资源。

　　5.1、innodb存储引擎概述

　　innodb支持常见的两种索引，B+树索引和hash索引。hash索引是自适应的，不能认为干预。

　　B+树是由平衡二叉树演化而来，但是B+树不是一个二叉树。

　　B+树并不能直接找到具体的行，B+树索引只能找到数据行所在的页，然后数据库通过把页读入内存，再在内存中进行查找。

　　5.2、二分查找法

　　页中的具体行就是通过二分法查找的。1946年发明的二分查找法，直到1962年才出现完整正确的二分查找法。

　　5.3、平衡二叉树

　　平衡二叉树首先的符合二叉树定义，其次必须满足任何节点的左右两个子树高度最大差1.平衡二叉树的效率较高，但是维护平衡二次树需要消耗比较多的资源。

　　5.4、B+树

　　B+树是从B树和索引顺序访问方法演化而来。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各页节点指针进行链接。

　　5.4.1、B+树的插入操作

　　B+树的插入必须保证插入后页节点中的记录依然排序，并且需要考虑插入B+树的三种情况。

　　leaf page full index page full 操作

　　NO NO 直接插入leaf page。

　　YES NO 1、拆分leaf page 2、将中间的节点放入index page中 3、小于中间节点的记录到左边 4、大于等于中间节点的记录到右边

　　YES YES 1、拆分left page 2、将中间的节点放入index page中 3、大于等于中间节点的记录到右边 4、拆分index page 5、小于中间节点的记录到左边 6、大于中间节点的放右边 7、中间节点放上一层index page

　　如果看不懂的请参照P166.

　　B+树总会保持平衡，但是对于新插入的值可能需要大量拆分，这样会消耗大量磁盘资源，所以B+树有了旋转(rotation)功能，旋转发生在leat page已经满了，但是其左右节点没有满的情况下，这时B+树并不会着急去拆分页的操作，而且是将记录转移到所在页的兄弟节点上，通常左兄弟先被检查。

　　5.4.2、B+树的删除操作

　　B+树使用填充因子(fill factor)来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样必须保证删除后页节点中的记录依然排序，同插入一样B+树删除操作也需要考虑三种情况。

　　leaf page below fill factor index page below fill factor 操作

　　NO NO 直接将记录从页节点删除，如果该节点还是index page的节点，则用该节点右边节点代替

　　YES NO 合并页节点及其兄弟节点，同时更新index page

　　YES NO 1、合并页节及其兄弟节点 2、更新index page 3、合并index page及其兄弟节点

　　5.5、B+树索引

　　B+树索引在数据库中有一个特点是高扇出性(fan out),B+树的高度一般是2-3层。B+树索引可以分为聚集索引(clustered index)和辅助聚集索引(secondary index)。

　　聚集索引：即表中数据按照主键顺序存放，而聚集索引就是按照每张表的主键构造一颗B+树，并且叶节点中存放着整张表的行记录数据。

　　辅助索引：也称为非聚集索引，叶级别不包含行的全部数据，叶节点除了包行键值以外，每个叶级别中的索引行中还包含了一个书签，该书签就是对应行数据的聚集索引键。

　　5.6、B+树索引的使用 P183 (联合索引可以只使用左边那个，或者同时使用左边+右边，但是不能单独使用右边的索引)

　　5.7、hash索引

　　innodb存储引擎中自适应hash索引使用的是散列表(hash table)的数据结构。但是散列表不只存在于自适应hash中，每个数据库中都存在，用来加速内存中数据的查找。

　　5.7.1哈西表(hash table)

　　hash table又叫散列表，由直接寻址表改进而来。