索引采用的数据结构
<ul>
<li><a href="https://www.bilibili.com/video/BV1pA411H7Vd?p=7">https://www.bilibili.com/video/BV1pA411H7Vd?p=7</a></li>
</ul>
<h2>mysql为什么不使用哈希表</h2>
<ul>
<li>哈希冲突会造成数据散列不均匀，会产生大量的线性查询，比较浪费时间</li>
<li>不支持范围、当进行范围查询时，必须挨个遍历</li>
<li>对内存空间要求较高</li>
</ul>
<h2>mysql中哈希索引</h2>
<ul>
<li>memory存储引擎</li>
<li>InnoDB存储引擎支持自适应哈希</li>
</ul>
<h2>mysql树分类及mysql最终选择的树</h2>
<ul>
<li>二叉树
<ul>
<li>每个结点有且只有两个分支</li>
<li>每个结点是无序的</li>
</ul></li>
<li>BST
<ul>
<li>binary serach tree 二叉搜索树</li>
<li>插入数据时，必须有序，左子树必须小于根节点，右子树必须大于根节点</li>
<li>使用二分查询，提高查询效率</li>
</ul></li>
<li>AVL(平衡二叉树)
<ul>
<li>AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构</li>
<li>如果插入数据是递增或递减顺序时，怎么办？</li>
<li>退化成链表，查询复杂度为O(n)</li>
<li>经过左旋或者右旋，让树平衡起来，就是平衡二叉树</li>
<li>平衡二叉树要求最短子树与最长子树高度不能超过1</li>
<li>为保证平衡，在插入数据时必须要旋转，通过插入性能的损失来弥补查询性能的提升</li>
</ul></li>
<li>红黑树
<ul>
<li>基于平衡二叉树，如果读写请求一样多时，引入红黑树</li>
<li>经过左旋或者右旋，让树平衡起来，还有变色行为</li>
<li>最长子树高度不超过最短子树高度2倍即可</li>
<li>查询性能与插入性能取得近似一致</li>
</ul></li>
<li>B树
<ul>
<li>把有序二叉树变成有序多叉树，每一个节点可以存放多个数据值</li>
<li>如果存储更多数据，需要在B树基础，继续增加节点，树的深度又会变深，I/O量就会继续增加</li>
</ul></li>
<li>B+树
<ul>
<li>子叶节点存储数据，非子叶节点不存储数据</li>
<li>mysql的B+树一般是最多3到4层，保持key的长度越小越好，存储数据量就越大</li>
<li>面试问题：创建索引时，字段类型使用int好，还是使用varchar好</li>
<li>取决于int和varchar取支持的长度是多少，</li>
<li>如int(4)，int为4字字节，varchar(5)，varchar为5字节，就使用int类型，由于int的4字节小于varchar的5字节</li>
<li>mysql索引使用B+树</li>
</ul></li>
</ul>
<h2>mysql为什么要使用B+树</h2>
<ul>
<li>二叉树，红黑树，B树等数据结构，随着数据的插入，发现树的深度会变深，树的深度越深，意味着I/O次数越多，影响数据读取效率</li>
<li>树的深度尽量小决定的，提高读取效率</li>
</ul>
<h2>B+树注意</h2>
<ul>
<li>在B+树有两个头指针。一个头指针指向根节点，一个头指针指向关键字最小叶子节点，所有叶子节点(数据节点)之间是一种链式环结构</li>
<li>B+树进行两种查找运算
<ul>
<li>对于主键的范围查找和分页查找</li>
<li>从根节点开始，进行随机查找</li>
</ul></li>
</ul>
<h2>磁盘块数据组成</h2>
<ul>
<li>key</li>
<li>value，每一行完整记录</li>
<li>指针，如果匹配不到，下一个磁盘块在什么地方</li>
</ul>
<h2>数据结构思路练习</h2>
<ul>
<li>数据结构可视化网站
<ul>
<li><a href="https://www.cs.usfca.edu/~galles/visualization/Algorithms.html">https://www.cs.usfca.edu/~galles/visualization/Algorithms.html</a></li>
</ul></li>
<li>
<p>选择平衡二叉树</p>
<ul>
<li><a href="https://www.cs.usfca.edu/~galles/visualization/AVLtree.html">AVL Trees (Balanced binary search trees)</a></li>
</ul>
</li>
<li>选择红黑树
<ul>
<li><a href="https://www.cs.usfca.edu/~galles/visualization/RedBlack.html">Red-Black Trees</a></li>
</ul></li>
</ul>
<h2>谈一下你对mysql索引的理解</h2>
<ul>
<li>索引加快数据访问</li>
<li>底层数据结构
<ul>
<li>B+树，相比其他树结构来说，层次没有那么深，降低I/O读写次数</li>
</ul></li>
<li>存储引擎
<ul>
<li>索引与存储引擎相关，不同存储引擎在磁盘存储的形式也不一样。</li>
</ul></li>
<li>索引分类
<ul>
<li>主键，唯一，普通，全文，组合</li>
<li>组合索引遵循最左匹配原则</li>
</ul></li>
<li>
<p>索引还涉及到几个名词</p>
<ul>
<li>回表，索引覆盖，索引下推</li>
</ul>
</li>
<li>索引优化
<ul>
<li>主要使用explian命令进行优化</li>
</ul></li>
</ul>