数据库：索引

索引就相当于我们书本的“目录”

他是针对查询操作引入的优化手段，可以通过索引来加快查询速度，避免针对表进行遍历。

使用select查询：

1.先遍历表

2.把当前的行带入到条件中，看条件是否成立

3.成立则保留，不成立则跳过。

如果表非常大，那么遍历成本就很高，至少O（N）；

数据库把数据存储到硬盘上，每读取一个数据，都要读取硬盘，开销很大

索引的缺点：

1.占用更多空间:生成索引需要一系列的数据结构，以及额外的数据，存储到硬盘空间中。

2.可能会降低插入、修改、删除的速度

实际开发中：读多于写

索引的操作

1.查看索引： show index fron 表名；

主键、外键、被定义为unique唯一的都会自动创建索引。

一个表可以有很多个索引

2.创建索引： create index 索引名字 on 表名（列名）；

注意：

创建索引是危险操作！

创建索引需要对现有数据进行大规模重新整理

如果当前表是一个空表，没有影响；

如果当前表是一个很大的表，就会把数据库服务器卡住。

一般创建索引是在创建表的时候规划好，如果用了很久再创建索引需慎重考虑！！！

非得创建的方法：

两台服务器，一台服务器放的原数据，另一台新的服务器创建同样的表，并且把表上的索引创建好；

把数据从原服务器导入到新的服务器上（这里可以控制导入速度，不会像直接创建索引那样影响服务器）；

之后就可以用新的服务器替代旧的服务器。

3.删除索引： drop index 索引名字 on 表名；

手动创建的索引可以手动删除；

但是自动创建的索引（主键、外键、unique）不能删除

索引通过一定数据结构来实现

哈希表：只能进行精准匹配，不能进行模糊查询

顺序表：擅长通过下标访问，尾插

链表：擅长中间位置插入和删除

红黑树：可精准匹配，可范围查询，可模糊匹配

数据库引入的是B+树

B树

B树是一个N叉搜索树（要求有序），在二叉搜索树里进行了扩展（ 一个节点可能包含n个值，n个值划分出n+1个区间）

同样高度的树，相比于二叉搜索树能表示的更多。

同一个节点的这些key都是一次硬盘io出来的。即使总的比较次数增加了，但是硬盘的io次数减少了（一次硬盘io相当于内存中1w次比较）。

B+树

特点：

• 所有数据记录都保存在叶子节点，非叶子节点只存储索引（key，不存value）

• n叉搜索树，一个节点存在N个key，划分成N个区间。

• 叶子节点通过链表连接，形成一个有序链表，方便范围查询

• 所有叶子节点在同一层，树高低一致，查询效率稳定

• 每个节点中关键字按递增排列

• 非叶子节点的第 i 个关键字是其第 i 个子树的最大值（或最小值的上界）

优点：

1.N叉搜索树，树的高度有限，降低IO的次数。

2.非常擅长范围查询

3.所有查询最终落到叶子节点，查询时间开销稳定；

   B树如果要查询的元素在根节点或者层次比较高的节点，时间开销就少；反之则长

4.因为叶子节点是全集，会把行数据只存储到叶子节点上。

   非叶子节点只是存储一个用来排序的key（比如存个id）。

   非叶子节点占用空间少，我们将叶子节点存到硬盘，进行查询的时候缓存到内存中，这样的话可以在内存中进行，进一步减少了IO访问次数。

查找操作：

1.从根节点依次查找下去，知道叶子节点；

2.非叶子节点起辅助作用，查找路径唯一。

在 MySQL 的 InnoDB 引擎中：

• 主键索引（聚簇索引） 就是 B+树，叶子节点存的是整行数据

• 辅助索引（二级索引） 的叶子节点存的是主键值，回表再查整行

B树和B+树的区别