索引组织表

索引组织表(Index Organized Table)
索引组织表不是一种“组织表”
索引组织表是由索引“组织起来的”表
InnoDB中，表都是根据主键顺序组织存放的

索引(Index)
索引是数据库中对某一列或多个列的值进行预排序的数据结构
索引可以理解为数据的“目录”
InnoDB中，主键是一个特殊索引字段

主键(Primalry Key)
lnnoDB存储引擎表中，每张表都有一个主键:
若表中有一个非空唯一索引 (Unique NOT NULL)，即为主键
若有多个非空唯一索引，选择第1个定义的索引
若无，InnoDB自动创建一个6字节的指针，作为主键（rowid）

lnnoDB数据表均为索引组织表
索引组织表中的数据，被主键的索引组织起来

主流索引查找算法

线性查找Linear Search
时间复杂度O(N)
从第一个数据开始，逐个匹配
二分查找Binary Search
时间复杂度O(logN)拿出有序数列中点位置作为比较对象
根据中点数据大小，选取一半数据作为新的数列
每次可以将数据量减小一半
二叉查找树 Binary Search Tree
时间复杂度O(logN)
使用经典的二叉树数据结构
由根节点开始查找
可能退化为线性查找
平衡二叉树AVL Tree
查找时，与二叉搜索树相同
增删改时，通过旋转操作，维护树的平衡
B树 B Tree
B树是线性数据结构和树的结合
B树通过多数据节点大大降低了树的高度
B树不需要旋转就可以保证树的平衡
B+树 B+Tree
B+树是由B树发展而来的一种数据结构
B＋树的所有数据均在叶子节点
B+树的所有数据形成了一个线性表

B+树是目前最主流的数据库索引算法
B+树由线性表、二叉树、B树发展而来
B+树集成了线性表、平衡二叉树的优势

B+树索引
InnoDB使用B+树作为索引的数据结构
B+树的高度一般为2-4层，查找速度非常快
InnoDB索引分为聚簇索引(主索引)和辅助索引

聚簇索引Clustered Index
根据表的主键构造一个B+树
叶子节点直接存放行数据，而不是指针
索引组织表中，数据也是B+树的一部分

辅助索引
Secondary Index每张表可以有多个辅助索引
叶子节点并不包含行数据
叶子节点记录了行数据的主键，用来指示数据位置

InnoDB索引分为聚簇索引(主索引)和辅助索引
在同层B+树节点之间，为双向链表
在B+树节点之内，数据条目之间为单向链表
所谓索引即数据，是把数据直接记录在了主索引里

InnoDB的逻辑存储结构

表空间(tablespace)
表空间指的是数据表在硬盘上的存储空间
默认，所有表的数据都存在共享表空间
每个表的数据也可以放在独占表空间(ibd文件)

段(segment)
数据段:B+树的叶子节点
索引段:B+树的非叶子节点

区(extent)
区是由连续页组成的空间，大小为1MB（默认64页）
一次从磁盘申请4~5个区

页(page)
页是InnoDB中磁盘读写的最小逻辑单位，默认16KB
一个数据页就是一个B+树的节点(B+Tree Node)
页的大小充分考虑了机械硬盘和SSD的最小单元(512B和4KB)

InnoDB的逻辑存储结构为表空间、段、区、页、行
InnoDB的逻辑存储结构充分考虑了以基于B+树的表结构
InnoDB中的页是InnoDB自身的逻辑概念，与硬件的页无关

lnnoDB中的变长列

长度不固定的数据类型:
VARCHAR、VARBINARY、BLOB、TEXT
占用空间大于768Byte的不变长类型:
CHAR
变长编码下的CHAR

行溢出数据

由于lnnoDB每个数据页容量有限，导致数据字段也是有限的
当数据字段过大时，InnoDB会使用行溢出机制
行溢出机制会把超长字段放入单独开辟的数据页

lnnoDB行记录格式Row Format

InnoDB行记录格式主要分为两个时代:
Redundant / Compact (Antelope文件格式)
Dynamic / Compressed (Barracuda文件格式)
目前默认使用Dynamic，由Compact发展而来

索引的左侧用法

联合索引
使用两个或以上字段生成的索引
联合索引也可以加速“最左前缀”的查询
联合索引可以代替最左侧字段的单独索引
“带头大哥不能死，中间兄弟不能丢”

字符串的前缀索引
如果字符串过长，可以考虑使用前缀索引节约空间
如果前缀区分度太小，可以考虑两种变通方法:
倒序存储
新建Hash字段

字符串like
(like %关键字%) (like %关键字）会使索引失效
(like关键字%)左模糊才可以使用索引

lnnoDB约束数据的方法

Primary Key / Unique Key
通过将数据字段设置为索引，约束数据内容
Primary Key:唯一，不为NULL
Unique Key:唯一
唯一约束插入时的性能开销较大
Foreign Key
外键可以对数据的正确性实现约束
会影响性能，数据异常修复时比较麻烦
Default /NOT NULL
Default :数据默认值
NOT NULL:数据不为空
索引主字段尽量约束not null，字段的值是null是没法排进索引的，导致索引效率降低
触发器
插入、修改数据时，使用触发器校验数据
容易干扰业务，使用很少

InnoDB有多重约束数据方法
将数据设置为索引字段可以约束数据的唯一性，但开销较大
外键可以对数据有效性进行校验
NOT NULL的行为可能受到sql_mode参数的影响(innodb_strict_mode OFF 时无效)

视图View

使用视图可以创建不存在的虚拟表
视图的原理是预设一个SELECT语句
SELECT语句的查询结果作为虚拟表的数据

视图算法的选择
MERGE，将视图SQL合并到主查询SQL中
TEMPTABLE，将视图作临时表（中间结果)）来处理
一般来讲，MERGE的性能优于TEMPTABLE

无法使用MERGE的SQL
聚集函数
DISTINCT
GROUP BY
HAVING
UNION,UNION ALL
子查询

视图可以在不改变原有数据的情况下，创建虚拟表
尽量使用MERGE算法，并避免无法使用MERGE的SQL

总结
增加每页数据量:
尽量做到冷热数据分离，减小表的宽度
优先选择符合存储需要的最小的数据类型
避免行溢出:
把 BLOB 或是TEXT列分离到单独的扩展表中
禁止在数据库中存储图片，文件等大的二进制数据
控制B+树高度:
尽量控制单表数据量的大小，建议控制在500万以内