面试题：关于数据库索引

-----------简译。

源=http://20bits.com/article/interview-questions-database-indexes

 

-----------问题

解释一下什么是数据库索引，和它的工作原理。

 

-----------回答

数据库索引是一种辅助数据结构，它能加快数据提取速度。

索引是针对某列数据的，比如查询“列出所有姓Smith的人”会很快。

 

如果硬盘上有个文本文件，如何从中找出姓Smith的呢？

 

查找的代码可以如下：

results = []

for row in rows:

if row[2] == 'Smith':

results.append[row]

 

找满足条件的记录需要检查每行数据是非符合条件。

这个算法和数据的行数成正比。

很多数据库的表可能含有几百万或几亿行数据，这个算法就行不通了。

 

如何加快查找速度呢？用数据库索引。

 

任何类型的数据结构，如果能支持快速访问，都可以被看作索引。

常见索引：Hash索引，B-tree索引。

 

-----------Hash索引

参照上例，找姓Smith的人，我们可以建一个hash表。hash表的key就是last_name，value可以是指向数据行的指针。

 

这类索引就叫hash索引。很多数据库都支持这里索引。

但是它不常用。为什么？

考虑另一个查询：找所有45岁以下的人。hash索引可以处理等于关系，但不处理小于或大于关系。

给你2个的hash索引，它无法判断那个值更大，只能判断它们是否相等。

 

-----------B-tree索引

数据库中最常用的是B-tree索引。它是一种自平衡的tree。

B-tree的主要好处是它允许对数阶复杂度的查找、插入和删除。

和hash索引不同之处在于，它存的数据是有序的，这样能处理小于、大于和前缀的查询。

 

-----------其它索引

数据库中，其它类型的索引还有R-tree[MySQL支持]。

R-tree索引用于查询空间数据，比如，查找所有离San Francisco, CA. 10英里之内的城市。

 

还有bitmap索引，它的读取速度很快，但是比较占存储空间。适用于值稀疏分布的列。

 

-----------Performance

索引加快了查询速度，但是要付出代价。

比如表的插入和删除速度会减慢，因为需要更新索引。

如果表需要不断更新，索引很可能会导致performance问题。

还有空间代价。索引会占用内存或磁盘空间。

单个索引比表小，因为它不存所有的表数据，而是存相应的指针。

但表越大，索引通常也会跟着变大。

 

-----------设计

B-tree中的节点包含一个值和一个指向子节点的指针。

数据索引的值实际上是一对值：field值和指向某行的指针。

比如，某个对age的索引，B-tree的值可以是这样：(34, 0x875900)。

这样索引可以被存在内存中。

 

B-tree索引的每个节点占用一个磁盘块。这样每个节点通过一次磁盘操作就能被完全读取。

 

很多数据库用B+ tree，而不是B-tree。InnoDB的BTREE索引类型就更近于B+ tree。

another day