Database-索引原理

发表于 | 分类于 | |

数据库的索引原理。

为什么需要索引

假设以下查询:

1
2
SELECT * FROM Employee 
WHERE Employee_Name = 'Jesus'

如果没有索引，则需要对整张表进行遍历，效率极低。因此，索引是通过极大地减少需要检索的行/记录数的方式，来加速查询检索的速度。

索引的定义

索引是一个数据结构(一般情况下是 B-Tree)，其储存了表特定列的值。

B-Tree

B-Tree 是最常用的索引数据结构，因为其非常高效：

  • 所有的查找、删除、插入指令都能在对数(log)时间内完成;
  • 储存的数据可以进行排序。

B-Tree 本质上是一种平衡多叉树，其对子节点的数量限制是维持一个区间，因此可以避免过于频繁地树结构调整，保持一定的灵活性，但是也会引入一些空间冗余。

Algorithm-RTree

Hash Table

Hash Table 是另外一种可以用于索引的数据结构，原因同样是其在进行查找时，非常高效。

例如，上面的查询语句，Hash Table 可以存储这样的键值：

1
<Key:Jesus, Value:0x28938>

其中，Value存储的内存中的指针，指向硬件中数据表的某行，这样通过Key就可以快速查找到该行。

但是，Hash Table 也有其缺点，就是其 Key 是不能进行排序的。因此，类似这样的查询是无法支持的。

1
age > 40

R-Tree

R-Tree 常用于空间/距离相关问题的索引数据结构。例如，“查找附近两公里内的星巴克”。 R-Tree 本质上是将空间分割成一个一个矩形，再建立矩形包含关系的平衡多叉树 B-Tree ，这样查找的时候，就能利用 B-Tree 的优点进行距离的快速检索。

Algorithm-RTree

Bitmap

Bitmap 常用于Boolean型值的列。

举例:

Name Sex Marital
Jay Male Unmarried
Jolin Female UnMarried
Kobe Male Married

如果要查询:

1
select * from table where Sex = 'Male' and Marital = 'Married'

使用 Bitmap 进行标识, 然后进行AND位操作即可:

RowID 1 2 3
Sex 1 0 1
Marital 0 0 1
AND 0 0 1

索引的原理

以 B-Tree 为例，其可以通过对某列值进行排序，并存储指向该行的指针，因此，在进行查找操作时，可以通过排序完的数据集进行快速查找，并通过指针获取到对应该行的其他数据。

索引的使用

创建单列索引

SQL 语句：

1
2
CREATE INDEX name_index
ON Employee (Employee_Name)

创建多列索引

SQL 语句：

1
2
CREATE INDEX name_index
ON Employee (Employee_Name, Employee_Age)

是否使用索引

数据库会先衡量是否存在索引，如果存在，再计算索引的命中率。在某些情境下，使用索引并不如直接检索全表，例如：

Sex
Male
Female

对于这一列，实际上，只有两种值，Male 和 Female，索引命中率计算公式为：

$$Selectivity\ of\ index = cardinality\ /\ (number\ of\ records) * 100\%$$

假设表有10000行，cardinality 代入 2， 计算结果为：0.02%，非常低，这种情况下，实际上，使用索引并不能提升效率。例如，我们要查找 Famele 的行，那么很可能有5000行满足条件，使用索引需要耗时，并且消耗资源，访问索引5000次，远不如直接检索全表来得快。

索引的代价

使用索引需要额外的代价：

  • 占用空间:索引是一种数据结构，其存储需要占用空间;
  • 需要更新:添加、删除或者更新数据时，同时需要更新索引。