索引

sql索引模型图

索引：提高数据的查询效率

问题一： 二叉搜索树更新和查询的时间复杂度均为O(logN)，那么为什么不用二叉搜索树作为索引模型却选择了B+树？

1.二叉树效率高，但是树高太高，每次指针查找大概率都是触发随机磁盘读,频繁的磁盘读取使得效率变低；

2.N叉树，把整棵树的高度维持在很小范围内，同时在内存中缓存前面若干层的节点，可以极大的降低访问磁盘的次数，提高读的效率；

问题二： N叉树的N值在mysql中可以被人工调整嘛？

1. 首先5.6以后可以通过控制page的大小间接控制；

2.计算方法，前缀索引，调整K大小；

有序数组：查询效率高，更新效率低；

哈希表：将数据存在数组对应得hash值的位置，解决hash冲突的方法是维护一个链表。

hash(key) ==> value 在数组中的位置