Interview-DB

发表于
数据库

索引类型

Ordered Index

Primary index ( Clustering index ) 和 Secondary index ( Non-clustering index )

聚集索引：物理存储顺序和索引顺序相同，或者称主索引。降低插入删除性能，因为涉及到数据移动。 非聚集索引：物理存储顺序和索引顺序不一定相同。必须是稠密索引。

非聚集索引的查找结果是指向聚集索引的，所以需要再查一次才能找到具体的数据在哪里，所以查询速度更慢。

稠密索引 (Dense Index) 和 稀疏索引 (Sparse Index)

稠密索引：每个搜索码对应一个数据记录 稀疏索引：只有部分搜索码直接对应一个数据记录。比如将搜索码排序后分组，只记录每个组的最小搜索码，查找是找到比查询值小的最大搜索码，然后顺序查找找到对应数据记录。

为什么用B+/B树做索引

  1. 多叉vs二叉：首先普通的搜索树肯定不行，会退化为链表，所以要用平衡的搜索树。那么常用的红黑树是二叉树，对于给定n个值，树的高度由order（叉数）决定，记\(k=order\)，那么树的高度\(h=\log_{k}n\)。显然，多叉树的高度远小于二叉树。
  2. B+树 vs B树：B树的数据可以存储在叶子节点和非叶子节点，而B+树的数据一定存在叶子节点，这种设计使得B+树可以很方便地将数据顺序连接起来。B树确实提高了IO性能（把树节点载入到内存中，这些树节点按顺序放在磁盘中，每次顺序读取，减少寻道次数和读取次数），到那时不能顺序访问，所以提出了B+树来解决这个问题。