树形结构，是指：数据元素之间的关系像一颗树的数据结构。我们看图说话：
它具有以下特点：
维基百科中列举了计算机科学中树形结构的种类
233酱当然不会一个个讲，我们只挑一些熟悉的面孔：多叉树，二叉树，二叉查找树，红黑树，堆，Trie树，B树，B+树，LSM Tree，了解他们在对不同规模的数据 增，删，改，查 时所起到的作用就够了。
限于篇幅，本文主要介绍非LSM Tree的内容。
树体现了一种 继承 的关系，节点之间为父子关系。多叉树 是指一个父节点可以有多个子节点。也就是：爸爸可以有多个儿子，儿子只能有一个爸爸。
当需要这种分层，继承的场景下均可以考虑用树结构来实现，可以简化我们对数据关系的描述。
此外，节点的每个分支也代表着一种选择，可以用来做决策。
应用场景： 1.Linux文件系统 2.组织关系表示，如公司的组织架构，角色权限系统等。 3.XML/HTML数据。 4.类的继承关系 5.决策，如游戏中怪物使用的技能选择，机器学习…
二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构，也就是说 爸爸 最多只能有 两个儿子。
因为计算机应用中存在很多“非黑即白”的场景，同样我们可以利用 不是走左分支，就是走右分支 这种结构选择来做一些决策。 另外，利用每个节点下参与方最多为两个，也可以做一些事情。> 应用场景：
1.编译器的语法树构造。 2.表达式求值和判断：非叶子节点为操作符，叶子节点为数值。 3.Boolean求值，如
<span style="letter-spacing: 1px;">（a and b）or (c or d)。 4.霍夫曼编码 5.IPv4路由表的存储…
在我们的日常开发中，经常需要对数据进行增删改查，每一个步骤的时间空间效率决定了应用最终的性能。
时间效率 体现在 能否快速定位到要操作的数据元素，核心在于 索引的好坏；
空间效率 体现在 能否占用 更小的内存空间，能否利用计算机各层介质的缓存性能提高访问速度（访问速度：CPU>> 内存>>磁盘）。
在以下树形结构的讨论中，希望小伙伴能多从 索引，所占用内存空间，操作的介质 这些方面考虑数据的增删改查性能。
二叉查找树（Binary Search Tree）首先是二叉树，同时满足一定的有序性：节点的左子节点比自己小，节点的右子节点比自己大。
这样当我们定位一个元素的位置时，从根节点开始查找，小于节点左拐，大于节点右拐。等于节点排序值就刚好找到。二分的索引思想就体现在其中。
应用场景： 二叉查找树的有序性是它能够广泛应用的原因。但是能否高效二分体现在树的高度合理性上。下面要讲的 红黑树/堆结构才是其广泛应用。
二叉查找树的缺点在于：只限制了节点的有序性，但有序树的构造有好坏。一颗“坏”的有序树直接会被拉成 “有序链表”。所以需要通过一定的条件保证树的平衡性。
树的平衡性是指整棵树的最高子树和最矮子树相差不大，这样整棵树的高度相对来说低一些，相应的增，删，改，查操作的效率较高较稳定（与树高有关）。
红黑树（Red–black tree）是应用很广泛的一种平衡树，是面试官的装X利器。我们来看一下它保证平衡性的一些特性：
此外相比其他的平衡树：如高度平衡树AVL树，红黑树的增删改效率较高，同时查找性能没有下降很多也比较稳定。所以工业级应用更为广泛。
应用场景：适合排序，查找的场景。 1.容器的基本组成，如Java中的HashMap/TreeMap. 2.Linux内核的完全公平调度器 3.Linux中epoll机制的实现…
堆是一种特殊的数据结构，它满足两个特性：
这里解释一下完全二叉树。它是指：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
这样我们就可以用数组来存储。
假设根节点在i=0的位置：如果父节点的数组下标为i，则左子节点的数组下标为2 * i+1，右子节点的数组下标为 2 * i + 2。数组比链表的存储好处上篇文章233酱提过了，这里就不赘述了。
针对第2点，如果每个节点的值都大于等于子树中每个节点值的堆，叫做“大顶堆”。反之叫做“小顶堆”。
应用场景： 1.堆排序 2.TopK,求中位数，求 3.合并多个有序小文件或集合 4.优先队列，如定时任务的存储等…
Trie树 又称前缀树或字典树，它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
它的特性为：
如果我们有and,as,at,cn,com这些关键词，那么构建的trie树如下：
但是Trie 树的缺点就是构造Trie树需要很大的内存空间。因为父子字符节点之间用 指针关联。如果用数组保存这些指针，这意味着子节点的数组需要穷举出每一种可能。如子节点字符为a-z，就需要分配长度为26的数组来存储这些可能的子节点。
改进内存分配的措施有：
1.子节点指针改为用：有序数组、跳表、散列表、红黑树来存储。 2.子节点合并，如原来 hello存储为：h->e->l->l->o ,现在可存储为：h->e->llo
Trie 树毕竟比较浪费空间，所以它在字符串的查找中，适合用于：1.字符集不能太大 2.字符串的公共前缀较多 的场景。
应用场景： 1.关键词匹配，提示，纠错。 2.最长公共前缀匹配。 3.命令自动补全，如zsh. 4.网址浏览历史记录。 5.手机号码簿查询…
B树、B+树 是数据库中经常出现的数据结构。对于数据库的增删改查效率，需要考虑的首要因素是：磁盘的IO访问次数。
如何减少IO访问次数？
前文我们已经提到了索引，但是IO一次不容易，从磁盘中获取数据通常是以块为单位的。如果对于上千万条数据，我们只建立一层索引结构的话，那索引的数据量也是巨大的。
如何降低索引量？
假设我们到全世界找一个人，我们是按照 国家/省/市/区/街道/小区的顺序来定位。同理，随着数据量的增大，我们需要一层层的建立 多级索引 。越上层的索引每个块中表示的数据范围越大。
如何保证我们建立的多级索引 是“合适”的？
这个合适主要指：存储的数据量大并且树高小。同红黑树一样，我们需要一些 限制条件 来保证树高。这也就是以下数据结构的限制条件原因了。
一个m阶（该树每个节点最多有 M 个子节点）的B树具有以下特征：
1.根节点至少有两个子女。 2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m 3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m 4.所有的叶子节点都位于同一层。 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个子节点包含的元素的值域分划。
一个3阶的B树插入示意图如下：
应用场景：MongoDB
一个m阶的B+树具有以下特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。 2.所有的叶子节点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
看不懂没关系，我们只需要知道这些限制条件是为了让B+树数据“矮而胖”就好。
这里我直接放张掘金小册《从根儿上理解MYSQL》B+树主键索引的示意图：
应用场景 1.Mysql InnoDB存储引擎。
看到这里常考面试题来了：B树和B+树有什么区别？为什么Mongo用B树？为什么Mysql用B+树？
看图说话，B树 和 B+树显著不同的地方是： 1.B树非叶子节点即是索引，也是数据；B+树非叶子节点仅是索引，数据全部存储在叶子节点。 2.B+树叶子节点的数据之间是用链表链接的。 这会导致：
B+树相比B树：
1.数据的连续性：B+树叶子节点上一页存储的数据是连续的，当需要一个节点上的数据时，B+树可以增大缓存的命中率。
2.叶子节点之间的连接性：当作范围或全文扫描时，B+树可以依赖叶子节点做线性顺序扫描，而B树只能在每一层的节点上做扫描。B+树同样可以增大缓存的命中率。
B树相比B+树： 当作单一数据查询时，B树的节点平均离根节点更近，平均查询效率比B+树快。
总结一下：B+树相比B树，前者更适合范围查询，后者更适合单一数据查询。
Mongo是非关系型数据库，数据之间的关系用嵌套解决。它的主要使用场景是：追求 单个读写记录的性能。
Mysql是关系型数据库，数据之间的关系用共同的索引键，Join解决。它的使用场景：不仅存在大量的单一数据查询，也存在大量的范围查询。
所以上面的问题可以简单扯一扯了吧。
参考资料：
本文由哈喽比特于4年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/0JNjNOxQ7VBnDXgfuJ14FQ
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而，京东官方通过微博发言人发布的消息澄清了这些传言，称这些言论纯属虚假信息和蓄意捏造。
日前，据博主“@超能数码君老周”爆料，国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道，荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦（ASML）CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候，抖音悄然上线了一款名为“青桃”的 App，Slogan 为“看见你的热爱”，根据应用介绍可知，“青桃”是一个属于年轻人的兴趣知识视频平台，由抖音官方出品的中长视频关联版本，整体风格有些类似B站。
日前，威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”，同时，他发文表示：中国汽车普及率低于非洲国家尼日利亚，每百户家庭仅17户有车。意大利世界排名第一，每十户中九户有车。
近日，一项新的研究发现，维生素 C 和 E 等抗氧化剂会激活一种机制，刺激癌症肿瘤中新血管的生长，帮助它们生长和扩散。
据媒体援引消息人士报道，苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后，3D系统一度大涨超10%，不过截至周三收盘，该股涨幅回落至2%以内。
9月2日，坐拥千万粉丝的网红主播“秀才”账号被封禁，在社交媒体平台上引发热议。平台相关负责人表示，“秀才”账号违反平台相关规定，已封禁。据知情人士透露，秀才近期被举报存在违法行为，这可能是他被封禁的部分原因。据悉，“秀才”年龄39岁，是安徽省亳州市蒙城县人，抖音网红，粉丝数量超1200万。他曾被称为“中老年...
9月3日消息，亚马逊的一些股东，包括持有该公司股票的一家养老基金，日前对亚马逊、其创始人贝索斯和其董事会提起诉讼，指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息，为推广自家应用，苹果现推出了一个名为“Apps by Apple”的网站，展示了苹果为旗下产品（如 iPhone、iPad、Apple Watch、Mac 和 Apple TV）开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价，引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金（Future Fund）管理合伙人加里·布莱克发帖称，降价是一种“短期麻醉剂”，会让潜在客户等待进一步降价。
据外媒9月2日报道，荷兰半导体设备制造商阿斯麦称，尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效，但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日，根据美国证券交易委员会的文件显示，苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元（约 4.65 亿元人民币）。用于在 2023-2025 年期间，发射卫星，进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道，马斯克旗下社交平台𝕏（推特）日前调整了隐私政策，允许 𝕏 使用用户发布的信息来训练其人工智能（AI）模型。新的隐私政策将于 9 月 29 日生效。新政策规定，𝕏可能会使用所收集到的平台信息和公开可用的信息，来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日，荣耀CEO赵明在采访中谈及华为手机回归时表示，替老同事们高兴，觉得手机行业，由于华为的回归，让竞争充满了更多的可能性和更多的魅力，对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能（AI）系统，该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日，非营利组织纽约真菌学会（NYMS）发出警告，表示亚马逊为代表的电商平台上，充斥着各种AI生成的蘑菇觅食科普书籍，其中存在诸多错误。
社交媒体平台𝕏（原推特）新隐私政策提到：“在您同意的情况下，我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上，各大企业都带来了最新的理念和产品，而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品，具体内容为：“以我对我‘子公司’的了解，我认为 iPhone 15 跟 iPhone 14 不会有什么区别的，除了序（列）号变了，这个‘不要脸’的东西，这个‘臭厨子’。
