谈谈数据库索引

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

• 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问题。

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

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

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

设计

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

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

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

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

B-tree索引的每个节点占用一个磁盘块。这样每个节点通过一次磁盘操作就能被完全读取。
很多数据库用B+ tree，而不是B-tree。InnoDB的BTREE索引类型就更近于B+ tree。