无涯教程网

Database 数据库索引及其 BigO 表示法

发布于01月15日

我试图用大O符号来理解数据库索引的性能.在不太了解的情况下，我猜:

查询主键或唯一索引将为您提供O(1)查找时间.
查询非唯一索引也会产生O(1)时间，尽管"1"可能比唯一索引(？)慢.
在没有索引的列上查询将提供O(N)查找时间(全表扫描).

这大体上是正确的吗？查询主键是否会产生比O(1)更差的性能？我特别关心SQLite，但我也很想知道不同数据库之间的差异有多大.

推荐答案

大多数关系数据库将索引 struct 为B树.

如果一个表有一个聚类索引，那么数据页将存储为B树的叶 node .从本质上讲，聚类索引变成了表.

对于没有聚类索引的表，表的数据页存储在一个堆中.任何非聚集索引都是B树，其中B树的叶 node 标识堆中的特定页面.

B-树的最坏情况高度是O(logn)，由于搜索依赖于高度，B-树查找的运行方式大致如下(平均)

O(对数_tn)

其中t是最小化因子(每个 node 必须具有至少t-1个密钥和最多2*t*-1个密钥(例如，2*t*个子 node ).

我就是这么理解的.

当然，不同的数据库系统很可能在幕后使用不同的数据 struct .

当然，如果查询不使用索引，那么搜索就是对包含数据页的堆或B树的迭代.

如果使用的索引能够满足查询，则搜索会稍微便宜一些；否则，需要后备来获取内存中的相应数据页.

Database相关问答推荐

Power BI中的计数

如何将对象源动态设置为子窗体

TYPO3 OOPS，出现错误！编码：202402180809040864ba5c

是否有一个简单的工具可以将 mysql 转换为 postgresql 语法？

在 model.save() 中处理竞争条件

递归关系的数据库设计

Objective-C中是否有类似于LINQ的东西？

何时将数据库称为嵌入式数据库？

SQL 概念 LEFT OUTER JOIN 和 WHERE NOT EXISTS 基本相同吗？

当可伸缩性无关紧要时，NoSQL 与 SQL

错误：mysqlnd cannot connect to MySQL 4.1+ using the old insecure authentication

MS Access 迁移的前端？

什么是表前缀？

如何更改 MySQL DB 中所有表的前缀？

SQL 中的 CAST 和 CONVERT 是否相同？

如果表不存在，如何使用 Derby Db 创建表

在 SQLite 数据库中加入 3 个表

MySQL 中 NOW()、SYSDATE() 和 CURRENT_DATE() 之间的区别

数据库触发器的命名约定

做或不做：将图像存储在数据库中

实用课程推荐

相关教程推荐