首页
精选文章红黑树查看全文红黑树是一种含有红黑节点并能自平衡的二叉查找树，其具有良好的效率，查找、增加、删除等操作都可以在 O(logN) 时间内完成。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 都是用了红黑树。红黑树的特征如下： 每个节点要么是黑色，要么是红色。 根节点是黑色。 每个叶子节点（NIL）是黑色。 每个红色结点的两个子结点一定都是黑色。 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。该特征可以推出如果一个结点存在黑子结点，那么该结点肯定有两个子结点。 有序 如果树结构要实现查询功能，那么树结构一定是要求有序的。 二叉查找树（BST，binary search tree），就是在二叉树的基础上增加有序性，有序的二叉树可以用来快速的查找、删除、插入元素。 二叉树实现有序的方式是左子树节点的值都小于根节点的值，右子树节点的值都大于根节点值，这里的根节点不只特指树的根节点，包括所有的非叶子结点。 但是二叉查找树的缺点是数据可能会出现倾斜，例如构建树的过程中，结点是从小到大顺序传入的，树会退变为一个链表，查找元素的事件复杂度会从左右子树的高等相等时候的O（log(n)）变为O（n）。 平衡 如果树结构需要满足查找高效稳定，要求树结构一定是平衡的。平衡性是指对任意非叶子结点而言，其左子树和右子树的高度基本相同，最多相差一。 二叉平衡树（AVL），就是二叉查找树的基础上增加了平衡性。 二叉平衡树在插入或者删除节点的时候，需要维持树的平衡，实现的复杂度较高。 稳定 如果要满足树结构的增删效率，要求树结构在变化的时候尽量只影响局部…Context【Golang】查看全文对于分布式系统的交互，除了调用时明确的参数传递之外，传入一些上下文信息是一个良好的工程实践，上下文中可以传入本次调用的一些环境信息，例如发起的IP地址，发起的请求等。因为分布式系统调用的拓扑关系一般是一个有向无环图，所以上下文也同样存在层级关系或者父子关系，下游的上下文带有上游上下文传入的所有信息，还可以加入自己的信息。 由于存在父子关系，所以上下文除了信息传递之外还可以进行一些控制信息的传递，例如传递超时，取消信息，一旦一个节点的上下文触发了取消，取消信息可以传播给其所有的子孙节点。 Golang的context就是上述上下文的一种实现，Golang的协程之间存在各种较为复杂的关系，比如一个通道的关闭可能会触发多个协程的关闭，还有微服务场景下更为复杂的级联关系，比如http执行过程会可能会启用一个新的协程发起rpc调用，如何优雅的管理这些协程的退出，例如在请求已经超时的情况，把整个调用链的协程全部关闭，Context就可以承担这个功能。 context是golang中定义的一个接口context包中提供了context接口的一些实现类，例如emptyCtx，valueCtx，cancelCtx，timerCtx等。 emptyCtxClickhouse查看全文clickhouse是俄罗斯搜索公司 Yandex开源的一款分析型数据库，主要用于OLAP场景。clickhouse不兼容大数据领域的hadoop生态，但是以高性能，功能支持完备而有众多拥趸。广泛应用于商业智能，电信行业，以及电商商务，社交等场景。clickhouse一直以性能出色著称，在10亿条数据量的情况下，clickhouse的单表聚合查询性能可以达到MySQL的将近1000倍。 clickhouse不支持事务，对行维度数据的查询，删除，更新能力支持一般。 clickhouse数据存储的基本单元和关系型数据库一致，都是表存储，其拥有完备的DBMS功能： DDL：可以动态的创建，修改或者删除数据库、表以及视图 DML：可以动态的查询，插入，修改或者删除数据 权限控制，可以按照用户纬度设置数据库的库/表操作权限。 提供数据备份，恢复以及分布式集群管理模式。 clickhouse的性能在同类型的MPP数据库中属于翘楚，得益于以下的设计。 列式存储 列式存储相较于行式存储，更方便数据压缩，而且对系统缓存也能更加高效的利用。Clickhouse默认采用LZ4压缩算法，该算法的压缩比可以得到8:1，但是性能高于一般的压缩算法。 列式存储也能够有效减少查询时候的扫描的数据量。 列式存储不支持select *等查询语法 向量化执行引擎 数据库查询执行最著名的是火山模型，也是在各种数据库系统中应用最广泛的模型。SQL查询在数据库中经过解析，会生成一棵查询树，查询数的每个节点为代数运算符(Operator)。火山模型把Operator看成迭代器，每个迭代器都会提供一个next() 接口。 一般Operator的next… |
热门分类开源Golang消息队列JavaJavascriptLinuxMysqlNLPPHP事务内存管理分布式理论分类存储常用存储开源软件操作系统画图网络编程数据库算法虚拟化前端存储理论常用算法微服务数据结构算法应用计算机原理中间件共识算法分布式分治动态规划容器并发排序架构组件绘图工具网络协议编程语言理论算法思想树缓存架构C++字符串算法工程思想搜索
算法题库
精选内容 |
