数据库索引的作用及原理

数据库索引是附加到表字段的标识符，以提高查询速度。 很多人机械地理解索引的概念，认为添加索引只有好处，没有坏处。 事实上，远非如此。 这里我就尽可能详细的介绍一下。

首先，了解为什么索引可以提高速度。 DB执行Sql语句时，默认的方式是根据搜索条件扫描全表，遇到匹配条件则添加搜索结果集。 如果我们对某个字段添加索引，那么在查询时，我们会首先定位索引列表中具有特定值的行数，这样就大大减少了遍历的匹配行数，因此可以显着提高查询速度。 那么是否应该随时添加索引呢？ 下面举几个反例： 1、如果每次都需要获取所有表记录，而且无论如何都必须进行全表扫描，那么添加索引就没有意义了。 2、对于非唯一字段，比如“性别”，有大量重复值，添加索引是没有意义的。 3、对于记录比较少的表，添加索引不会带来速度优化反而会浪费存储空间，因为索引需要存储空间，而且有一个致命的缺点就是每执行一次//，字段索引的更新就必须重新计算。

那么什么时候添加索引合适呢？ 我们看一下Mysql手册中给出的一个例子。 这是一个SQL语句：

，来自 c，用户 u WHERE = u。 和c。 >= 0 AND LIKE '%i%' AND u. IN (g.FROM g WHERE g.='')这条语句涉及到3张表的join，并且包含了很多搜索条件如大小比较、Like匹配等。在没有索引的情况下Mysql需要执行的扫描次数为rows 。 我们给 和 字段添加索引后，扫描的行数只有134行。 在Mysql中，可以通过查看扫描次数。 可见，在这种联表和复杂搜索条件的情况下，索引带来的性能提升远比其占用的磁盘空间更重要。

那么索引是如何实现的呢？ 大多数数据库供应商基于数据结构——B 树来实现索引。 因为B树的特点是适合在磁盘等直接存储设备上组织动态查找表。 B树的定义如下： m(m>=3)阶的B树是满足以下条件的m叉树：

1. 每个节点包括以下范围（j, p0, k1, p1, k2, p2, ... ki, pi）其中j是关键字的数量，p是子指针

2.所有叶子节点都在同一层，层数等于树高h。

3、每个非根节点包含的关键字数量满足[m/2-1]