索引与算法
索引与算法
InnoDB存储引擎支持的索引：B+树索引、全文索引、哈希索引。
B+树中的B不是二叉(binary)，而且平衡(balance)。B+树是从平衡二叉树演化而来。
数据结构与算法
二分查找法(binary)
也称为折半查找法，用来查找一组有序记录中的某个值。基本过程：将所有记录有序排序，先以有序序列中的中间点位置为比较对象，如果要找的元素小于中点元素，则将待查部分缩小到左半部分(排序为递增的情况)，否则为右半部分。通过一次比较，将查找区间缩小一半。
图中为二分差48的过程。对于这个序列中的数字来说，二分查找的平均查找次数为(4+3+2+4+3+1+4+3+2+3)/10=2.9次，顺序查找的评价查找次数为(1+2+3+4+5+6+7+8+9+10)/10=5.5次。
上图为一棵二叉查找树，数字代表每个节点的键值。左子树的键值均小于根节点的键值，右子树的键值均大于根节点的键值。通过中序遍历的输出为：2、3、5、6、7、8.
对于上述数列，顺序查找的平均次数为(1+2+3+4+5+6)/6=3.3次，二叉查找树的评价查找次数为(3+3+3+2+2+1)/6=2.3次。但是二叉查找树的建立任意的，如果树的结构如下图，
那么，平均查找次数为(1+2+3+4+5+6)/6=3.16次，显然并没有比顺序查找好多少。
平衡二叉树，首先是符合二叉查找树的定义，然后必须满足任何两个节点的子树高度最大差为1。这样，平衡二叉树的查询效率就很高了。
但是平衡二叉树建立和维护的代价是很大的。每一次更新、新增或者删除数据，需要多次的左旋或者右旋来保持更新后树的平衡性。
B+树
在B+树中，所有记录节点都是按照键值的大小顺序存放在同一层的叶子节点中，由各叶子节点指针进行连接。
B+树的插入操作
在上图中的B+树中插入28这个值，发现当前的LeafPage和IndexPage都有空闲，直接插入即可。插入完成如下：
在插入70这个值，原来的LeafPage已经满了，但是IndexPage还没有满，这时插入之后LeafPage的情况就是50、55、60、65、70.依据中间的值60来拆分叶子节点。结果如下：
最后插入95这个值，此时LeafPage和IndexPage均满了，需要做两次拆分，结果如下：
由上，可以看出B+树不管怎么变化，都是平衡的。且B+树插入有以下3种情况：
B+树的删除操作
B+树使用填充因子(Fill Factor)来空值树的删除变化。50%是填充因子可设置的最小值。B+树的删除操作同样必须保证删除后叶子节点种记录有序。同插入一样B+树的删除有以下三种情况：
在上述插入完成之后的树种删除70这个值，删除后的结果如下：
再删除25这个记录，由于此值为IndexPage中的值，删除之后需要将28更新到IndexPage中。删除后的结果如下图：
最后删除60，删除LeafPage种60的记录之后，Fill Factor小于50%，需要合并。同样再删除IndexPage中的记录之后也需要合并操作。最终结果如下：
B+树索引
数据库中的B+树索引可以分为聚集索引和辅助索引，不论是聚集还是辅助，其内部军事B+树，即高度平和的，叶子节点存放在所有的数据。不同的是，聚集索引的叶子节点存储整行信息，每张表只能有一个聚集索引；辅助索引的叶子节点不包含整行信息，一个表可以拥有多个非聚集索引。
聚集索引就是按照表的主键构造的一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点成为数据页。和B+树的数据结构一样，每个数据页都通过一个双向链表来进行连接。
辅助索引，也称为非聚集索引，叶子节点不包含行记录的全部数据。叶子节点除了包含键值，每个叶子节点的索引行中还包含一个书签。该书签用来告诉InnoDB存储引擎在哪里可以找到与索引相对应的行数据。
B+树索引的管理
索引的船舰和删除可以通过两种方法，ALTER TABLTE和CREATE/DROP INDEX.
使用CREATE/DROP INDEX，创建表t，并创建一个辅助索引。
除了整个列的索引，还可以只索引一个列数据开头的部分。如，使用ALTER TBALE为列b添加索引，只索引前100个字段。
除了单个列上的索引，还可以添加联合索引。如下，对列(a,c)添加联合索引idx_a_c：
查看表中索引的信息：SHOW INDEX FROM tableName;
可以看到t表上有4个索引，分别是主键索引、c列上的辅助索引、b列上的开头100字节的辅助索引和(a,c)的联合辅助索引。
>各字段的含义
Table:索引所在表的名称。
Non_unique:非唯一的索引，其中primary key是0，因为必须是唯一的。
Key_name:索引的名称。
Seq_in_index索引中该列的位置，联合索引idx_a_c较为明显。
Column_name:索引列的名称。
Collation:列以什么方式存储再索引中，可以是A或NULL,B+数索引总是A，即排序的。如果使用Heap存储，并建立了Hash索引，就显示NULL了，因为Hash根据Hash桶存放所有数据，不需要排序。
Cardindlity:表示索引中为一只的数据的估计值，Cardindlity表的行数尽可能接近1，如果非常小，那么用户需要考虑是否可以删除此所有。
Sub_part:是否是列的部分被索引，如果是整个字段，显示的为NULL。
Packet:关键字如何被压缩，没有压缩为NULL。
Null:索引的列是否含有NULL值。idx_b为yes，因为列B运行为NULL。
Index_type:索引的类型。InnoDB存储引擎只支持B+数索引，所以均显示BTREE。
Comment:注释
Index_comment:注释
哈希算法
哈希表
假设某应用需要一个动态集合，每个元素都有一个取自全域U的关键字，同时每个元素的关键字都唯一。
用一个数组表示(即直接寻址表)T表示动态集合，其中每个位置对应全域U中的一个关键字。位置k指向集合中的一个关键字为k的元素，如果该集合没有关键字为k的元素，则T[k]=NULL.
如果当域U较大时，直接寻址分配给T的空间就很大，或者计算机的整个空间都不够T来使用。
哈希表(Hash Table)或散列表解决了直接寻址存在的问题。将关键字通过哈希函数映射到数组T的某个位置，如果有多个元素映射到同一个位置，那么将这些映射到同一位置的元素的哈希值用链表存储。
自适应哈希索引
InnoDB存储引擎使用哈希算法对字典进行查找，其冲突机制采用链表的方式，哈希函数采用除法散列方式。
自适应哈希索引经哈希函数映射到一个哈希表中。因此对于字典类型的查找非常迅速。可以通过SHOW ENGINE INNODB STATUS;来了解自适应哈希索引的使用信息。
自适应哈希索引有InnoDB存储引擎控制使用，不由DBA进行干预。
全文检索
全文检索(Full-Text Search)是将存储在数据库中的整篇文章中的任意内容查找除了。可以根据需要获取文章的段、句、词等信息。也可以进行统计和分析。
倒排索引
倒排索引和B+树索引一样，也是一种索引结构。它在辅助表中存储了单词和单词本身在一个或多个文档中所在位置之间的映射。