数据库索引
为什么要使用索引
快速查询数据。
什么样的信息能成为索引
能把数据记录限定在一定查找范围的字段(主键、唯一键以及普通键等)。
索引的数据结构
一般使用B+树做存储索引。
B+树一些主要的特点：
- 字数指针和关键字个数相同（读写代价更低）
- 非叶节点的字数指针P[i]，指向关键字值[K[i], K[i+1]）的子树
- 非叶节点仅用来做索引，数据都保存在叶子节点 （查询效果更稳定）
- 每个叶子节点都有一个指针指向下一个叶子节点(便于选择指定区间的元素，有利于对数据库进行扫描)
优点：
- B+树的读写代价更低
- B+树的查询效率更稳定
- B+树更有利于对数据库进行扫描
Hash表优点和缺点：
- 优点
- B+树需要执行多次IO操作才能找到目标的数据记录，而Hash表只需进行一次IO操作
- 缺点
- 仅能满足=、“IN”操作，不能进行范围查询（<、>、between and）。
- 不能用来避免数据的排序操作
- 不能进行部分索引键的查询
- 不能避免表的扫描
- 遇到大量数据的hash值相同时，可能效率会低于B+树
密集索引和稀疏索引
密集索引
每个数据记录的键值分别对应一个索引项
稀疏索引
- 只有一部分数据记录的键值有索引项对应。
- 为了定位一条数据记录，需要首先找到小于等于目标记录的最大索引，之后从这一项开始进行顺序遍历，直到找到目标记录为止。
区别
稠密索引的查询速度更快，稀疏索引占用的空间更小，且更容易插入和删除等。
查看30道真题和解析