B+ 树索引 #
没有索引的查找 #
没有索引的时候是怎么查找记录的？比如：
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
在一个页中的查找 #
如果表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：
-
以主键为搜索条件 在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
-
以其他列作为搜索条件 对非主键列，数据页中并没有对非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始 依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
在很多页中查找 #
大部分情况下表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：
- 定位到记录所在的页。
- 从所在的页内中查找相应的记录。
由于并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，每一个页中再使用上面一个页中的查找方法。非常 低效。
索引 #
先建一个表：
mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec)
简单的索引方案 #
根据某个搜索条件查找一些记录时为什么要遍历所有的数据页？
因为各个页中的记录并没有规律，我们并不知道搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。
那么，如何快速定位记录所在的数据页？
也可以建一个目录：
B+ 树 #
聚簇索引 #
- 使用记录主键值的大小进行记录和页的排序
- B+ 树的叶子节点存储完整的用户记录（记录中存储了所有列的值，包括隐藏列）。
具有这两种特性的 B+ 树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这就是所谓的索引即数据，数 据即索引。