第十单元 索引与视图
1. 常见的数据结构1. 栈（stack）
特点：先进后出，后进先出
2. 队列（Queue）
特点：先进先出
3. 数组（Array）
[*]查询速度快：通过地址值与索引可快速定位到数据
[*]删除效率低：删除数据后，要将每个数据前移
[*]添加效率极低：添加位置后，每个数据都后移，再添加数据。
4. 链表
[*]链接中的数据都是游离存储的，每个元素节点包含元素值与下一个元素的地址
[*]查询速度慢，因为每次查询都要通过head 指针依次查询
[*]添加，删除效率相对较高，因为只需要将指针重新指向新添加进来的元素，其他元素的位置不需要动。
5. 二叉树
二叉树，全名叫二叉搜索树。存入的数据以第一条数据为基准，小于放左，大于放右。
[*]只能有一个根节点，每个节点最多支持两个直接子节点
[*]节点的度：节点拥有的子数的个数。节点的度数不大于2，如果度数为0，则称为叶子节点或者终端节点。
[*]二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
[*]二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
缺点：
虽然二叉树可以提高一些效率，但是面对节点多时，或者树的深度很高时，还是会面临着查找速度慢的情况，而且还很容易出现退化链表情况（ 存放数据是有序 的时候）。
6. 平衡二叉树
数据结构在线地址： Data Structure Visualization (usfca.edu)
平衡二叉树是在满足二叉查找树的情况下，尽可能的让树的度数变低，以提高查询效率。
要求：任意节点的两个左右子树高度差不超过1，任意节点的左右子树都是一个平衡二叉树。
他底层在二叉树的基础上，对进行插入和删除操作时通过特定操作(如左旋转，右旋转等)保持二叉查找树的平衡，从而获得较高的查找性能。
什么是左旋转，右旋转呢？<br>左旋转：被旋转的节点从左侧上升到父节点<br>右旋转：被旋转的节点从右侧上升到父节点
缺点：
[*]树的深度过高，还是查询慢
[*]无法解决回旋查找问题。
[*]添加节点效率过低，因为节点旋转有可能牵一发而动全身
7. 红黑树
红黑树是一种自平衡的二叉查找树，是计算机中用到的一种数据结构，1972年出现，当时又被称为“平衡二叉B树”。1978年被修改为“红黑树”。每一个节点可以是红或者黑；红黑树不是通过高度平衡的，它的平衡是通过“红黑规则”进行实现的。
红黑规则：
[*]每一个节点或是红色的，或者是黑色的，根节点必须是黑色。
[*]如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
[*]对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
[*]如果一个节点没有子节点或者父节点，则该节点的相应指针属性值为Null,这些Null视为叶节点，叶节点是黑色。
添加节点：
[*]添加的节点的颜色，可以是红色的，也可以是黑色的。
[*]默认用红色效率高。（调整节点的次数会相对减少）
红黑树增删改查性能都比较好。
相对于要求严格的AVL树来说，它的旋转次数变少，所以对于搜索、插入、删除操作多的情况下，我们就用红黑树。
缺点： 虽然红黑树的深度已经较二叉树有所提升，但是当数据量过大时，如上万或者上百万条数据时他是深度会随之变高。效率较慢，而且红黑树和二叉树都有一个问题，就是回旋查找。
回旋查找
红黑树笔记中的案例图，要找比 6 小的数，它需要先找到6的位置然后回旋回去找父节点7,然后7还要去找5，然后一级一级找出所有小于6的数据 ，这样就十分缓慢 。
8. B 树
B树又称为多路平衡树。（Balance Tree），也叫B-树，他在树的基础上对节点进行横向的拉伸
B-树有如下特点:
所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
在关键字全集内做一次查找,性能逼近二分查找；
规则
[*]每个结点最多有m个棵子树（m 称为阶）
[*]除根结点外，其他每个分支结点至少有ceiling(m/2)棵子树 (ceiling 表示向上取整)
[*]根结点至少包含两棵子树（除非B树只包含一个结点）
[*]所有叶结点在同一层上，B树叶结点可以外成是外部结点，不包含任何信息。
[*]有j 个孩子的非叶子结点恰好有 j-1 个关键字（关键码），关键码按递增次序排列。
9. B+树
也是一种多路搜索树，和B树类似，B+树是B-树的变体，但对B树的基础上，做了一些改变，类似于C/C++。
一棵m阶的B+树主要有这些特点：
<uldata-mark="-"><li >每个结点至多有m个子女;
<li >
非根节点关键值个数范围：ceiling⌈m/2⌉ - 1
页:
[1]