树
<ul>
<li>是由n（n>=1）个有限节点组成一个具有层次关系的集合。</li>
<li>把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。</li>
</ul>
<h2>特点</h2>
<ul>
<li>每个节点有零个或多个子节点；</li>
<li>没有父节点的节点称为根节点；</li>
<li>每一个非根节点有且只有一个父节点；</li>
<li>除了根节点外，每个子节点可以分为多个不相交的子树；</li>
<li>日常应用中使用比较树种类，是二叉树。 </li>
</ul>
<h2>二叉树特点</h2>
<ul>
<li>每个结点最多有两颗子树，结点的度最大为2。 </li>
<li>左子树和右子树是有顺序的，次序不能颠倒。 </li>
<li>
<p>即使某结点只有一个子树，也要区分左右子树。</p>
</li>
<li>二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，</li>
<li>二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。</li>
<li>二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，
<ul>
<li>例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。</li>
</ul></li>
</ul>
<h2>树分类</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>
</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>