B-tree and UB-tree - Scholarpedia
The B-tree is a dynamic high performance data structure to organize and manage large datasets which are stored on pseudorandom access devices like disks, (Bayer and McCreight 1972). The UB-tree is a multidimensional generalization of the B-tree. Invented in 1969, B-trees are still the prevailing data structure for indexes in relational databases and many file systems (Comer 1979), (Weikum and Voss
B-tree and UB-tree - Scholarpedia
The B-tree is a dynamic high performance data structure to organize and manage large datasets which are stored on pseudorandom access devices like disks, (Bayer and McCreight 1972). The UB-tree is a multidimensional generalization of the B-tree. Invented in 1969, B-trees are still the prevailing data structure for indexes in relational databases and many file systems (Comer 1979), (Weikum and Voss
VLDB 1999: 78-89
Cache Conscious Indexing for Decision-Support in Main Memory. Jun Rao, Kenneth A. Ross: Cache Conscious Indexing for Decision-Support in Main Memory. VLDB 1999: 78-89@inproceedings{DBLP:conf/vldb/RaoR99, author = {Jun Rao and Kenneth A. Ross}, editor = {Malcolm P. Atkinson and Maria E. Orlowska and Patrick Valduriez and Stanley B. Zdonik and Michael L. Brodie}, title = {Cache Conscious Indexing fo
第7回 性能改善の鍵、インデックスの特性を知る～B-treeとハッシュ （1）B-tree | gihyo.jp
SQLアタマアカデミー 第7回性能改善の鍵、インデックスの特性を知る～B-treeとハッシュ （1）B-tree はじめに データベースを扱う仕事をしていると、パフォーマンスの問題に悩まされることは日常茶飯事です。とくに最近は、データベースに格納されるデータ量が飛躍的に増え、サーバのCPUやメモリといったハード面の増強だけでは追いつかないことも多くあります。 そのようなケースに対応するため、DBMSは性能改善のための手段を多く用意しています。その中で最もコストパフォーマンスの良い方法が、インデックス（索引）です。アプリケーションにもハード構成にも影響を与えずに実行でき、うまくいかなければすぐに削除できるという手軽さが大きな魅力で、効果はしばしば絶大です。 インデックスにはいろいろな種類があり、またDBMSによってもサポートする種類に差がありますが、本稿では最も重要な2つを取り上げます。それ
開発メモ: オンメモリB+木による省メモリ連想配列
Kyoto Cabinet 1.2.2から加わったGrassDBは、オンメモリでページ管理を行うB+木を実装してメモリを節約しちゃう仕組みである。それを使ってJava、Python、Ruby、Perlなどのハッシュ（連想配列）機構を鬼のように省メモリにしてみる。頑張ればなんと20分の1になる。 前提 B木やその変種のB+木などは、キーの順序が近いレコード群を「ページ」という単位にまとめてシリアライズしてストレージに書き込むことで、入出力の頻度を減らして高速化することを意図している。メモリに比べて低速なストレージの上で大量のデータを管理するために使われる。多くのRDBMSやいくつかのDBMがB+木をサポートしているのはそれが理由であろう。一方で、メモリ上で検索可能なデータ構造を表現するためには、二分探索木やその特殊例である赤黒木が使われる。STLのstd::mapの実装にも赤黒木を使うのが一
Wayang88 - LINK RESMI LOGIN JOIN AGUSTUS 2024
Wayang88 : Profil Perusahaan Kasino Online Terkemuka 2024 Selamat datang di Wayang88, sebuah nama yang telah menjadi simbol kepercayaan dan hiburan berkualitas tinggi di dunia kasino online. Berdiri sejak tahun 2019 dan berpusat di Filipina, Wayang88 slot telah mengukir namanya sebagai destinasi utama bagi para penggemar kasino online di Indonesia. Dengan lisensi dan regulasi dari Philippine Amuse
INDEX FULL SCANを狙う - MySQL Casual Advent Calendar 2011 - SH2の日記
2011年8月のkazeburoさんのエントリに対する解説記事です。結論から言うとkazeburoさんの案に賛成なのですが、本日はどうしてそうなったのかというところを確認していきたいと思います。本記事はMySQL Casual Advent Calendar 2011の17日目のエントリです。16日目はakira1908jpさんでした。 当時の内容を覚えていない方は、先にkazeburoさんのエントリをご一読ください。また、テストケースがGitHubに公開されていますのでカジュアルに再現試験をすることも可能です。 Covering Index と self-join と MySQL - blog.nomadscafe.jp kazeburo's gist: 1150842 - Gist 問題のSQLをチューニングするには、MySQLがインデックスに対してどのようにアクセスするかという点につ
B Tree をいけにえの技法で - Tociyuki::Diary
単方向連結リストの中から eq で一致する要素を削除するとき、リストの頭にダミーのセルをくっつけておいてから、ループを回すのは常識の部類に属します。そうしておけば、一つ先が一致したところで、手前のセルからのリンクをすげかえることができるからです。 ⇒ 竹内郁雄「初めての人のためのLISP」, 1986, サイエンス社、ISBN4-7819-0454-8、141 ページ これをよく「いけにえの技法」と呼びます。 でも、それを「いけにえの技法」と呼ぶのか、それも「よく」呼ぶのかどうか。この本の元になった連載で初めてこの名称を目にした当時、御大のジョークの可能性高しと疑ったものです。実は今でも疑っています。名称についての真相はともかくとして、基本的には単方向連結リストのリンクのつけかえをするときに使う手法です。それでは、あまりに当たり前すぎておもしろくないので、ここではひとひねりして B Tre
Paper: A practical scalable distributed B-tree - High Scalability -
« The VeriScale Architecture - Elasticity and efficiency for private clouds | Main | How is Berkely DB fare against other Key-Value Database » We've seen a lot of NoSQL action lately built around distributed hash tables. Btrees are getting jealous. Btrees, once the king of the database world, want their throne back. Paul Buchheit surfaced a paper: A practical scalable distributed B-tree by Marcos
Google、STLのmap/setと互換性のあるコンテナをBツリーで実装した「C++ B-Tree」を公開 | OSDN Magazine
Googleは2月1日、mapやsetといったコンテナをBツリーで実装したC++テンプレートライブラリ「C++ B-Tree」のリリースを発表した。STLのmapやset、multimap、multisetとほぼ互換性のあるBツリー実装で、STLのmapやsetなどよりも消費メモリが少なく、またキー検索などの処理速度が向上しているという。 C++ B-TreeはB木（Bツリー）構造を使って実装されたC++向けコンテナライブラリ。STL（Standard Template Library）のmapおよびset、multimap、multisetと同様の機能を持つ「btree_map」および「btree_set」、「btree_multimap」、「btree_multiset」といったコンテナを提供する。 STLのコンテナは赤黒木（Red Black Tree）を用いて実装されることが多い。
幻塔戦記グリフォンの AI で使っている Behaviour Tree
こんにちは、クライアントエンジニアの Sindharta Tanuwijaya（シンダルタ タヌイジャヤ）です。 今更ですが、1月の社内の勉強会で、 Behaviour Tree という AI の手法を発表させて頂きました。当時は幻塔戦記グリフォンを開発するのにあたって、1つのフィーチャーを完成させるためにこの機能を作っていましたが、今はいろいろなフィーチャーで使われています。 Behaviour Tree とは思考 AI のアルゴリズムの1つで、比較的に良く知られているステートマシンと目的が似ています。それはゲーム内のオブジェクトをどう考えさせて、行動させることです。ステートマシンも良い手法ですが、 AI が複雑になってくるのにつれて、管理の難しさが倍に増えるデメリットがあります。そこで、 Behaviour Tree を導入してみたわけです。 当日発表したスライドは以下です。 また、自
Causal Decision Trees
Uncovering causal relationships in data is a major objective of data analytics. Causal relationships are normally discovered with designed experiments, e.g. randomised controlled trials, which, however are expensive or infeasible to be conducted in many cases. Causal relationships can also be found using some well designed observational studies, but they require domain experts' knowledge and the p
ハミルトン閉路問題 - Wikipedia
ハミルトン閉路問題（ハミルトンへいろもんだい）とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。 概要[編集] 与えられたグラフが有向グラフ（グラフ理論参照）の場合は有向ハミルトン閉路問題、無向グラフ（通常のグラフ）の場合は無向ハミルトン閉路問題と呼ばれる。 この問題はどちらも、NP完全問題であることが知られている。また、無向ハミルトン閉路問題は巡回セールスマン問題の特殊ケースでもある。 始点と終点が一致するという閉路の条件を取り去ると、ハミルトン路問題になる。 NP完全性の証明[編集] ハミルトン閉路問題は NP完全問題の頂点被覆問題が有向ハミルトン閉路問題に多項式時間変換可能であることが証明され、さらに有向ハミルトン閉路問題は無向ハミルトン閉路問題に多項式変換可
立方体グラフ - Wikipedia
ピーターセングラフは立方体グラフである。 完全2部グラフ は2部立方体グラフの一例である。 数学のグラフ理論の分野における立方体グラフ（りっぽうたいグラフ、英: cubic graph）とは、すべての頂点の次数が 3 であるようなグラフのことを言う。言い換えると、立方体グラフとは 3-正則グラフである。立方体グラフは 3価グラフとも呼ばれる。2部立方体グラフ（bicubic graph）とは、立方体グラフかつ2部グラフであるようなグラフのことを言う。 1932年、ロナルド・フォスター（英語版）は、フォスター調査（Foster census）の皮切りとして、立方体対称グラフの例の集計をはじめた[1]。設備グラフやピーターセングラフ、ヒーウッドグラフ、メビウス-カントールグラフ（英語版）、パップスグラフ（英語版）、デザルググラフ（英語版）、ナウルグラフ（英語版）、コクセターグラフ（英語版）、ト
正則グラフ - Wikipedia
代数的属性[編集] あるグラフの隣接行列を A とする。そのグラフが k-正則であることは、ベクトル が固有値 k に属する A の固有ベクトルであることと同値である[1]。他の固有値に対応した固有ベクトルは と直交なので、そのような固有ベクトル について が成り立つ。 次数 k の正則グラフが連結していることと、固有値 k の重複度が1であることは同値である[1]。 正則な連結グラフの判定基準も存在する。グラフが連結かつ正則であることと、 である行列 J がそのグラフの隣接代数（Aの冪乗の1次結合）にあることは同値である。[要出典] グラフGはk-正則グラフで、直径D、隣接行列の固有値群は とする。Gが2部グラフでないなら、次が成り立つ。 ここで である。[要出典] 生成[編集] 正則グラフを生成するソフトウェアとして GenReg がある[2]。 脚注・出典[編集] ^ a b Cve
)
次数 (グラフ理論) - Wikipedia
各頂点に次数を記したグラフ グラフ理論における次数（じすう、英: degree, valency）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる[1]。頂点 の次数を と表記する。グラフ G の最大次数を Δ(G) と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(G) と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。 有向グラフでは、頂点に入ってくる辺数を入次数 (indegree)、頂点から出て行く辺数を出次数 (outdegree) と呼ぶ。 グラフ の次数の総和は次の公式で表される。 これの証明は double counting という手法（二通りに数え上げる）の例である。グラフ内の辺と頂点の接合の個数は式
頂点 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "頂点" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年2月） 頂点（ちょうてん、vertex）とは、角の端にある点のことである。多角形では2本の辺が接しているか交わっている点、多面体では3本以上の辺が共有している点のことをいう。直観的には図形の周上にある点のうち周辺のどの点よりも突出していて"尖った点"のことを頂点という。 図ではA,B,Cの3点が頂点 一般にn角形には頂点はn個あり、辺の本数に等しい。座標平面上にある図形ではその頂点を含む範囲で連続であっても微分不可能である。 また曲線が極大値や極小値をとる点のことを頂点という
閉路 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "閉路" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2012年7月） 閉路（へいろ、英: cycle）あるいは閉道（へいどう、英: closed path）とは、グラフ理論の始点と終点が同じ道であることを指す。すなわち、出発点に戻るような辿り方であって頂点の重複がないグラフのことである。グラフ理論や位相幾何学において用いられる。 閉路グラフ[編集] グラフの一種を言うこともある。n個の点vi（i=0, 1, ..., n -1）からなるグラフで、辺はちょうど、vi とvi+1（i=0, 1, ..., n -1添字はn を法とする）を結
全域木 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Spanning tree|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
B+ Tree Visualization