1 索引的本质：是数据结构，几种数据结构的比较

索引的本质
展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在
虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的

为什么不用二叉树或者红黑树？

假设有100万数据，他的高度特别高，2的平方=100万。树的高度为n .当查找的数据恰好在叶子节点的话，他需要n次磁盘io才能查找到元素。
不用的原因主要的问题就是树的高度没法控制。索引查找磁盘IO的影响特别大。
索引的本质

hash 表：

1>select * from t where t.clo1=6
1存储数据时，将数据存入通过哈希函数计算所得哪那个地址里面。
2查找时，使用同一个哈希函数通过关键字key计算出存储地址，通过该地址即可访问到查找的记录。只进行了一次磁盘IO。

2>但是当查select * from t where t.clo1>6 时就没有办法了。范围查询的话还得进行全表扫描。
所以在实际中也不会用hash .
索引的本质

2.B树

索引的本质
相对于红黑树，他的一个节点可以存储多个索引小元素。意外这存储相同的数据量，B树肯定比
红黑树的高度小的多。只有横向节点无限大，就可以控制他的高度就可以控制的很小。

那为什么不一个节点放所有的索引元素，只经过一次磁盘I/O?
假设500兆的数据，一次磁盘I/O 加载不了这么大的数据，即使能加载也得花多长时间，得多慢。同时这么大的数据加载到内存中，对空间很浪费。常用的数据也许只有20%。你却把整个表的所有索引元素都加载进去了，对内存空间是很浪费的。所以是不可取的。

mysql 官方对节点设置为16k
B树虽然解决了红黑树的问题，但是并没有解决范围查找的问题