数据库篇（七）——数据库的索引

一、数据库索引的原理

数据库索引的数据结构：

目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种B+树（数据库索引的首选数据结构）作为索引结构。
参考：https://blog.csdn.net/aqzwss/article/details/53074186

B-树

B-树是一种多路搜索树（并不一定是二叉的）
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

1、根结点至少有两个子女；

2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；

3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；

4、所有的叶子结点都位于同一层。

特点：

是一种多路搜索树（并不是二叉的）：

1.定义任意非叶子结点最多只有M个儿子；且M>2；

2.根结点的儿子数为[2, M]；

3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

5.非叶子结点的关键字个数=指向儿子的指针个数-1；

6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

8.所有叶子结点位于同一层；

优点：

• 关键字集合分布在整颗树中；
• 搜索有可能在非叶子结点结束；
• 其搜索性能等价于在关键字全集内做一次二分查找；
• 自动层次控制；

查找、删除、插入参考：https://blog.csdn.net/qq_35644234/article/details/66969238

B+树：

参考：https://blog.csdn.net/qq_35644234/article/details/67650285
B＋tree 是一个n叉树，每个节点有多个叶子节点，一颗B+树包含根节点，内部节点，叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上叶子节点的节点。

定义

• 其定义基本与B-树同，除了： 非叶子结点的子树指针与关键字个数相同；
• 非叶子结点的子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树 为所有叶子结点增加一个链指针；
• 所有关键字都在叶子结点出现；

优点

• B+-tree的磁盘读写代价更低，没有了中间索引，可以放下更多的数据
• 范围查找的时候从链表开始走

B＋tree的性质：

1.n棵子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的非终端结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。

B+树比B-树的优势

下面是B+树和B-树的一个对比截图：（来自：参考文件）

为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？（摘抄自：参考文件）

（1）B+tree的磁盘读写代价更低
B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree ( 一个结点最多8个关键字) 的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

（2）B+tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

B+树查找参考：https://www.phpsong.com/752.html

目前网站的访问速度限制都是在mysql上面，php虽然没有java的高，但是效率已经很高了，而mysql目前的负载都是集中在IO上面的，所以提高IO的速度都是提高了整个网站性能，有了索引大大的提高了mysql的执行效率。

二、数据库索引

数据库索引是用于提高数据库表的数据访问速度的。

数据库索引的优点：
a）避免进行数据库全表的扫描，大多数情况，只需要扫描较少的索引页和数据页，而不是查询所有数据页。而且对于非聚集索引，有时不需要访问数据页即可得到数据。
b）聚集索引可以避免数据插入操作，集中于表的最后一个数据页面。
c）在某些情况下，索引可以避免排序操作。
d）加速表与表之间的连接
索引的缺点：
a）需要占物理空间
b）对表中的数据增加、删除和修改时，也需要动态维护索引，降低了数据的维护速度。

问题：性别字段为什么不适合加索引？从B+树分析

尽量选择区分度高的字段作为索引，区分度的公式为count(distinct col)/count(*),表示字段不重复的比例，比例越大扫描的二级路越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据前区分度是0。在性别字段上增加索引，并不能明显增加检索速度。

三、索引有哪些？

1、唯一索引/非唯一索引

唯一索引：在一个表中由一个或多个字段组成的索引，这些字段组合起来在表中不可以重复。
非唯一索引：与唯一索引不同的是，这些字段组合起来在表中可以重复，不要求唯一。

2、主键索引（主索引）

是唯一索引的特定类型。表中创建主键时自动创建的索引，一个表只能有一个索引

3、聚集索引/非聚集索引

聚集索引（聚簇索引）：表中记录的物理顺序与键值的索引顺序相同，一个表只能有一个聚集索引。
非聚集索引：表中记录的物理顺序与键值的索引顺序不同。

聚集索引与非聚集索引的区别，分别在什么情况下使用？

根本区别是：表中记录的物理顺序与键值的索引顺序是否一致。

聚集索引的优点是： 查询速度快
聚集索引的缺点是：对表进行修改速度慢（因为在插入新纪录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效）
使用聚集索引的场合是：
- 某列包含了小数目的不同值
- 排序和范围查找
其他方面的区别：
- 都采用了B+树的结构，但非聚集索引的叶子层并不与实际的数据页相重叠，而采用叶子层包含一个指向表中的记录在数据页中的指针的方式。聚集索引的叶节点就是数据节点
- 非聚集索引添加记录时，不会引起数据顺序的重组。
使用非聚集索引的场合是：
- 此列包含了大数目的不同值
- 频繁更新的列

4、组合索引（联合索引）：

基于多个字段而创建的索引。

创建索引：
create index idx1 on table1(col1,col2,col3)
查询
select * from table1 where col1=A and col2=B and col3=C

可以使用联合索引的：左原则。