索引
为什么我们需要索引
加快数据库的查询速度。
实现
索引的基本原理：保存一些元数据作为路标，帮助我们快速查找数据。如果我们想要以不同的方式查找同一份数据，可能需要建立多份索引。
哈希：单行查询的时间复杂度是 O(1)，但是范围查询的时间复杂度会退化到 O(n)，而 SQL 有很多范围查询。
-
树：平衡树的增删查改的时间复杂度是 O(lg(n))，与树的高度成正比。但是，不同平衡树的区别是对磁盘IO的优化。
- 平衡二叉搜索树：（1）树的高度比较高，一次查询可能比较慢。（2）一个节点只存储了一条记录，需要多次磁盘IO。
- B 树：（1）m 叉树存储大量数据时，树的高度仍然比较低。（2）一个节点存储了多条记录，如果将一个节点的大小设置为磁盘页大小，例如 4K，可充分利用磁盘预读的特性，极大地减少磁盘 IO 次数。
- B+ 树：将叶子节点组成了一个有序链表，范围查询的效率比 B 树高。
优缺点
优点：大大加快查找数据的速度。
缺点：维护索引会产生额外的开销，特别是写入的时候。任何类型的索引都会减慢写入速度，因为每次写操作都会更新索引。所以，数据库通常不会为所有数据生成索引，需要程序员或DBA基于应用查询模式的了解来正确设置索引，以获取最大的收益。
