Database: Index

27th January 2021 at 8:21am
Database

关系型数据库的索引被用来加速数据的查找。

使用什么数据结构?

对比:

  • Hash Table:查单个数据时快;不方便落盘;数据多时内存可能不够用;不支持范围查询
  • 平衡树:支持范围查询;更新和查询性能好 O(log n);不方便落盘
  • B+Tree:支持范围查询;适合落盘;更新和查询性能好;本质上是以更多的分支来减少层高,从而使读写性能高

主流的 RDBMS 都使用 B+Tree。

操作的考虑点

  • 插入数据:页内数据可能被挪动;单页可能满,会有页分裂过程
  • 删除数据:页内容稀疏时会合并
  • 使用自增 ID 做插入操作时,key 的值总是增加,数据不需要挪动、页分裂时性能也好

MySQL 的 InnoDB 引擎的实现

InnoDB: Topic: Index