递增整数列：为什么需要索引来加速查询？
Column of increasing integers: why is an index needed to speed up the query?
在以下示例中，t 是一个递增序列，在 100 万行中大致从 0 到 5,000,000。
import sqlite3, random, time
t = 0
db = sqlite3.connect(':memory:')
db.execute("CREATE TABLE IF NOT EXISTS data(id INTEGER PRIMARY KEY, t INTEGER, label TEXT);")
for i in range(1000*1000):
t += random.randint(0, 10)
db.execute("INSERT INTO data(t, label) VALUES (?, ?)", (t, 'hello'))
选择具有索引的范围（假设 t = 1,000,000 ... 2,000,000）：
db.execute("CREATE INDEX t_index ON data(t);")
start = time.time()
print(list(db.execute(f"SELECT COUNT(id) FROM data WHERE t BETWEEN 1000000 AND 2000000")))
print("index: %.1f ms" % ((time.time()-start)*1000)) # index: 15.0 ms
比没有索引快4-5倍：
db.execute("DROP INDEX IF EXISTS t_index;")
start = time.time()
print(list(db.execute(f"SELECT COUNT(id) FROM data WHERE t BETWEEN 1000000 AND 2000000")))
print("no index: %.1f ms" % ((time.time()-start)*1000)) # no index: 73.0 ms
但数据库大小至少比索引大 30%。
问题：一般来说，我理解索引如何极大地加速查询，但是在 t 是整数 + 递增的情况下，为什么甚至需要索引来加速查询查询?
毕竟，我们只需要找到 t=1,000,000 的行（这在 O(log n) 中是可能的，因为序列是递增的），找到 t=2,000,000 的行，然后我们有范围。
TL;DR：当列是一个递增的整数序列时，有没有办法快速查询一个范围，而不必增加带索引的数据库大小增加 30%？
例如在创建table时设置一个参数，通知Sqlite该列正在递增/已经排序？
简短的回答是 sqlite 不知道您的 table 是按列 t 排序的。这意味着它必须扫描整个 table 才能提取数据。
当您在列上添加索引时，列 t 在索引中排序，因此它可以跳过前百万行，然后将感兴趣的行流式传输给您。您正在提取 20% 的行，它 returns 在 15 ms / 73 ms = 21% 的时间内。如果该分数越小，您从索引中获得的收益就越大。
如果列 t 是唯一的，则考虑使用该列作为主键，因为您将“免费”获得索引。如果您可以使用相同的 t 来限制行数，那么您可以使用 (t, offset) 作为主键，其中 offset 可能是一个 tinyint。关键是 size(primary key index) + size(t index) 会大于 size(t+offset index)。如果 t 以 ms 或 ns 为单位而不是 s，它在实践中可能是唯一的，或者您可以 fiddle 在它不是时使用它（当您需要数据时，只需 t运行 达到第二分辨率).
如果您不需要主键（作为唯一索引），请将其保留，只在 t 上使用非唯一索引。如果没有主键，您可以通过 rowid 标识唯一的行，或者如果所有列共同创建一个唯一的行。如果您创建没有 rowid 的 table，您仍然可以使用 limit 对相同的行进行操作。
您可以使用数据库仓库技术，如果您不需要每条记录的数据，请以更细粒度的方式存储它（每分钟或每小时记录，group_concat 文本列）。
最后，还有针对时间序列数据优化的数据库。例如，它们可能只允许您删除最旧的数据或添加新数据，但不能进行任何更改。这将允许系统存储预先排序的数据（mysql，顺便说一句，将此功能索引称为有序 table）。由于数据无法更改，因此我的 运行-length 或 delta 数据库按列压缩数据，因此它仅存储行之间的差异。
在以下示例中，t 是一个递增序列，在 100 万行中大致从 0 到 5,000,000。
import sqlite3, random, time
t = 0
db = sqlite3.connect(':memory:')
db.execute("CREATE TABLE IF NOT EXISTS data(id INTEGER PRIMARY KEY, t INTEGER, label TEXT);")
for i in range(1000*1000):
t += random.randint(0, 10)
db.execute("INSERT INTO data(t, label) VALUES (?, ?)", (t, 'hello'))
选择具有索引的范围（假设 t = 1,000,000 ... 2,000,000）：
db.execute("CREATE INDEX t_index ON data(t);")
start = time.time()
print(list(db.execute(f"SELECT COUNT(id) FROM data WHERE t BETWEEN 1000000 AND 2000000")))
print("index: %.1f ms" % ((time.time()-start)*1000)) # index: 15.0 ms
比没有索引快4-5倍：
db.execute("DROP INDEX IF EXISTS t_index;")
start = time.time()
print(list(db.execute(f"SELECT COUNT(id) FROM data WHERE t BETWEEN 1000000 AND 2000000")))
print("no index: %.1f ms" % ((time.time()-start)*1000)) # no index: 73.0 ms
但数据库大小至少比索引大 30%。
问题：一般来说，我理解索引如何极大地加速查询，但是在 t 是整数 + 递增的情况下，为什么甚至需要索引来加速查询查询?
毕竟，我们只需要找到 t=1,000,000 的行（这在 O(log n) 中是可能的，因为序列是递增的），找到 t=2,000,000 的行，然后我们有范围。
TL;DR：当列是一个递增的整数序列时，有没有办法快速查询一个范围，而不必增加带索引的数据库大小增加 30%？
例如在创建table时设置一个参数，通知Sqlite该列正在递增/已经排序？
简短的回答是 sqlite 不知道您的 table 是按列 t 排序的。这意味着它必须扫描整个 table 才能提取数据。
当您在列上添加索引时，列 t 在索引中排序，因此它可以跳过前百万行，然后将感兴趣的行流式传输给您。您正在提取 20% 的行，它 returns 在 15 ms / 73 ms = 21% 的时间内。如果该分数越小，您从索引中获得的收益就越大。
如果列 t 是唯一的，则考虑使用该列作为主键，因为您将“免费”获得索引。如果您可以使用相同的 t 来限制行数，那么您可以使用 (t, offset) 作为主键，其中 offset 可能是一个 tinyint。关键是 size(primary key index) + size(t index) 会大于 size(t+offset index)。如果 t 以 ms 或 ns 为单位而不是 s，它在实践中可能是唯一的，或者您可以 fiddle 在它不是时使用它（当您需要数据时，只需 t运行 达到第二分辨率).
如果您不需要主键（作为唯一索引），请将其保留，只在 t 上使用非唯一索引。如果没有主键，您可以通过 rowid 标识唯一的行，或者如果所有列共同创建一个唯一的行。如果您创建没有 rowid 的 table，您仍然可以使用 limit 对相同的行进行操作。
您可以使用数据库仓库技术，如果您不需要每条记录的数据，请以更细粒度的方式存储它（每分钟或每小时记录，group_concat 文本列）。
最后，还有针对时间序列数据优化的数据库。例如，它们可能只允许您删除最旧的数据或添加新数据，但不能进行任何更改。这将允许系统存储预先排序的数据（mysql，顺便说一句，将此功能索引称为有序 table）。由于数据无法更改，因此我的 运行-length 或 delta 数据库按列压缩数据，因此它仅存储行之间的差异。