数据库索引用于加快查询速度。虽然哈希索引具有O(1)的时间复杂度,而树索引为O(log(n)),但由于SQL操作中常有排序需求,因此数据库普遍采用树型索引。InnoDB引擎不支持哈希索引。数据预读的工作原理是磁盘按页预读取数据,以减少未来的磁盘IO操作。局部性原理指导软件设计,使得数据读取更高效。数据库中最常用的索引结构是B+树,适合磁盘存储,能充分利用预读特性,具有较低的树高度,且占用内存少,支持单点查询、范围查询和有序性查询。