为什么使用 B-Tree(B+Tree)

由于机械磁盘的特性,磁盘的存取速度比主存慢很多,往往是其的 几百分分之一,因此为了提高效率及减少磁盘 I/O,往往每次读取都会预读,即使读取一个字节,也需要从此往后读取一定长度的数据放入内存,预读的长度一般为页(page)的整数倍。而 B Tree 之所以高效,根据 B-Tree 的定义,可知检索一次最多需要访问 h 个节点,一次检索最多需要 h-1 次 I/O,渐进复杂度为 O(h) = O(logdN)。一般实际应用中,出度 d 是非常大的数字,通常超过 100, 因此 h 非常小(通常不超过3),所以 B-Tree 作为索引结构效率非常高

为什么使用 B-Tree(B+Tree)

comments powered by Disqus

Tags

abcs accept acid activemq affinity algorithm allocation android array async aws b+tree b-tree backoff benchmark best-practices bfs big-o bigquery bind bitcount blog break broker bubble buffer cache cap cert cgroups channel citus class classmethod cluster concurrency config consumer container context cookie cors crawler cronjob csrf ctr data-science data-structure database datadog dataflow datascience decorator defer dfs distributed django dns docker double-shipping drf ecosia elastic-search enumerate epoll errgroup extra fabric2 facebook-pixel financial-report flask flutter forward-proxy freelance frontend frp garbage-collector gc gcp generator get gil git golang goroutine graphql ha handbook haproxy hash hash-slot hashring hashtable hpa http http-auth http-proxy http_proxy https index init innodb instagram intergration interview ios javascript jinja2 jobboard jwt k8s kafka kibana kqueue label lambda layer4 layer7 lean levels.io linked-list linux list listen loadbalancer logs long-tail lru marketing master matplotlib memory merge metaclass metaprogramming metrics metrics-server microservices mitm model mq myisam mysql namespace nat netflix network-extension nginx nodejs nomad nosql npm oodesign openssl optimization orm pandas parallelism paramiko parkinglot patroni permission pg pipeline pixelme post postgresql postresql prefetch_related prerender private-key process proxy proxycommand put pvm python queue rabbitmq rbac react-native reactive reactjs rebase redis redis-cluster replication resource rest restfulapi retargeting retry revenue reverse-proxy rocketmq rsa rxswift saas scaleable search-engine security select seo serverless service session set shadosocks shadowsocks shard sharding shell shopify sigint signal sigterm slack slave slow-query sniper sns socket socks5 source-code spa sql sqlalchemy sqs ssh ssl ssl-pinning stack startup state stateful stateless staticmethod string struct swift switch syscall system-design systemctl tcp tcp-proxy thread tmpreaper token traefik trustkit tunning type typeform udp variable vc vpn vuejs web web-development where yarn zset 削峰 宽索引 异步 看源码学-golang 窄索引 解耦 跨域 跳板机



Archives

2019 (148)