参考:https://segmentfault.com/a/1190000010264071 在此基础上做了些总结

索引的定义:

帮助数据库高效地获取数据的数据结构

为什么索引:

数据库中的数据结构复杂.很多算法 如顺序查找、二叉树查找、二分查找等等都需要满足特定的数据结构才能使用,所以数据库就需要有一个满足这些算法的数据结构(索引)来高效滴获取数据

图1展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据

博主恶补数据结构中。。。

知识点:

B-Tree、B+Tree、B*树介绍
数据结构回顾:B、B-、B+、B*-Tree