• Tree-11-mysql index 数据库索引
  索引 MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。 提取句子主干，就可以得到索引的本质：索引是数据结构。 我们知道，数据库查询是数据库的最主要功能之一。 我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。 最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量...
  2020-10-17 08:15:55 | Data-Struct
• Tree-10-多路查找树 B* 树 及 java 实现
  B* Tree B* Tree 是 B+ Tree的变体，在 B+ Tree的非根和非叶子结点再增加指向兄弟的指针； B* Tree定义了非叶子结点关键字个数至少为 (2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。 实际例子 给出了一个简单实例，如下图所示： B+ Tree的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结...
  2020-10-17 08:15:55 | Data-Struct
• Tree-09-多路查找树 B+ 树 及 java 实现
  B+ 树的概念 B+ 树是应文件系统所需而产生的一种B Tree的变形树。 描述 B Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。 与B Tree相比，B+Tree有以下不同点： 每个节点的指针上限为2d而不是2d+1。 内节点不存储data，只存储key；叶子节点不存储指针。 图3是一个简单的B+Tree示意。 由...
  2020-10-17 08:15:55 | Data-Struct
• Tree-08-多路查找树 BTree 及 java 实现
  BTree 历史 在1970年，Bayer＆McCreight发表的论文《ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES》（大型有序索引的组织和维护）中提出了一种新的数据结构来维护大型索引，这种数据结构在论文中称为B Tree。 B树的定义 h：代表树的高度，k 是个自然数，一个B树要么是空的，要么满足以下条件： ...
  2020-10-17 08:15:55 | Data-Struct
• Tree-06- B 树之 2-3 Tree
  2-3 树 2–3树是一种树型数据结构，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。 2–3树由约翰·霍普克洛夫特于1970年发明。 2–3树和AA树是等距同构的，意味着它们是同一种数据结构。 换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。 2–3树是平衡树，意味着右边，...
  2020-10-17 08:15:55 | Data-Struct
• Tree-05-伸展树 Splay Tree 及 java 实现
  伸展树 伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊 O(log n) 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。 它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。 核心思想 考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小...
  2020-10-17 08:15:55 | Data-Struct
• Tree-04-图解红黑树 Red Black Tree 及 java 实现
  Red Black Tree 红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。 它是复杂的，但它的操作有着良好的最坏情况运行时间，...
  2020-10-17 08:15:55 | Data-Struct
• Tree-03-图解 AVL 自平衡二叉查找树及 java 实现
  AVL树 AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。 它是最先发明的自平衡二叉查找树（Self-balancing binary search tree），也被称为高度平衡树。 相比于”二叉查找树”，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。 例子 AVL 平衡树 5 2 7 1 3 6 9 ...
  2020-10-17 08:15:55 | Data-Struct