数据库索引的实现

数据库索引,目前有树索引、哈希索引、全文索引等。

索引

索引是数据之外的一种数据结构,专门用来查找表中数据。
使用索引,可以大大加快检索速度,相应的,有获得必须有付出,我们需要话费额外的空间来存储索引。

索引这玩意儿,不像烧饼,做好了吃完就没了,索引有许多的优点,如:加快检索速度,数据无重复,加快表与表间的连接速度,有序的索引方便连续值查找。

索引这玩意儿,和其它的东西一样,既有优点又有缺点,它的缺点有:,创建和维护索引耗费时间、存储索引需要空间。

树索引

商业化的数据库中,一般都支持树索引,B-Tree 或 B+Tree。(实际上 B+Tree 使用更多)

和哈希索引相比,树索引的查找速度最慢会达到 O(LogN),但树索引是有序的。

哈希索引

哈希索引基于哈希表实现,将所有索引列(有时不只给一列数据建索引,要给两列三列甚至更多列建索引)结合起来,从而为每一行数据算出一个尽量独一无二的哈希值。
哈希值和该哈希值对应的数据行的行指针组合在一起,便是哈希表中的一行数据,N 行数据一起就是哈希表。

处理冲突

每当两个不同的数据拥有相同的哈希值,就意味着出现了冲突。冲突出现后,哈希索引会将彼此冲突的数据们串连起来,形成巨长的一条链(请别忘记我永远不变黄色的脸)

优点:

查找速度高达 O(1)。

缺点

  1. 只保存哈希值和行指针,不保存数据库中的数据;查找数据时,先计算数据的哈希值,使用该值来查找行指针,找到行指针后还要到数据库中验证,确保该数据行就是要查找的数据,所以每次查找都要读行
  2. 哈希表数据无序,无法用于排序
  3. 不支持部分索引列查找(建立了两列的索引,那就没法只用一列的数据来查找)。
  4. 索引维护成本高(如果哈希冲突很多,每从表中删除一行就要遍历整条冲突链,以便删除目标行)。
  5. 哈希值可能冲突

全文索引

全文索引是一种特殊的索引,它并不直接匹配 Where 条件,不直接比较索引中的值,而是像搜索引擎那样,查找的是文本中的关键词。