1 分割の基本概念
1.1 数学における分割
1.1.1 集合の分割
集合の分割とは、ある集合を互いに素な部分集合の族に分割し、それらの和集合が元の集合に一致する操作を指す。形式的には、集合Xの分割とは、Xの部分集合からなる集合族Pであって、以下の条件を満たすものをいう。 * すべてのPの要素は空集合ではない。 * Pの任意の二つの要素は互いに素である（共通部分を持たない）。 * Pのすべての要素の和集合がXに等しい。
例えば、集合{1, 2, 3}の分割の一つに{{1}, {2, 3}}がある。集合の分割は、同値関係と密接に関連しており、同値類が自然な分割を構成する。
1.1.2 数の分割
数の分割（整数分割）は、正整数nを正整数の和として表す方法のうち、順序を区別しないものを指す。例えば、4の分割は5通り存在する：4, 3+1, 2+2, 2+1+1, 1+1+1+1。分割の個数はnの分割数p(n)として知られ、ラマヌジャンらによってその性質が深く研究されている。数の分割は組合せ論や数論において重要なトピックであり、ヤング図形を用いた視覚化がよく行われる。
1.2 データ構造における分割
1.2.1 配列の分割
配列の分割とは、一次元配列を複数の連続した区間（サブ配列）に区切る操作である。例えば、長さnの配列をk個の部分に分割する場合、各パーティションは連続したインデックス範囲を持つ。この操作は、クイックソートのピボット基準による分割や、メモリ管理におけるページ分割などで利用される。配列の分割は、分割位置の指定方法により、均等分割や任意分割など様々なバリエーションが存在する。
1.2.2 グラフの分割
グラフの分割は、グラフの頂点集合をいくつかの部分集合に分割し、各部分集合間の辺の数を最小化または制約する操作である。典型的には、グラフをk個の連結成分またはほぼ独立したサブグラフに分割する。この問題はNP困難であることが知られているが、メトロポリス法やスペクトラルクラスタリングなどの近似手法が実用化されている。グラフ分割は、VLSI設計や並列計算の負荷分散、ソーシャルネットワーク分析に応用される。
2 分割の応用分野
2.1 アルゴリズム設計
2.1.1 分割統治法
分割統治法は、問題をより小さな部分問題に分割し、各部分問題を再帰的に解き、その結果を統合して元の問題を解決するアルゴリズム設計手法である。分割と統合の過程が鍵であり、分割の品質が全体の効率に大きく影響する。
2.1.1.1 マージソートの分割
マージソートでは、配列を中央で二分し、二つの部分配列に分割する。この分割は常に均等に行われるため、再帰の深さはO(log n)になる。分割後、各部分配列を再帰的にソートし、その後マージ（統合）する際に整列された結果を得る。分割の均等性が安定したO(n log n)の時間計算量を保証する。
2.1.1.2 クイックソートの分割
クイックソートでは、配列からピボットを選び、要素をピボットより小さいグループと大きいグループに分割する。この分割はその場で行われ、均等分割が保証されないため、最悪の場合はO(n^2)となるが、平均的にはO(n log n)である。分割のバランスを改善するために、ピボットの選び方（中央値の中央値など）が工夫される。
2.2 データベース設計
2.2.1 水平分割
水平分割は、データベーステーブルの行を複数のテーブル（またはパーティション）に分割する手法である。各パーティションは元のテーブルと同じスキーマを持ち、特定の条件（例えば、IDの範囲やハッシュ値）に基づいて行が振り分けられる。水平分割により、大規模テーブルのクエリ性能が向上し、並列処理が容易になる。ただし、複数パーティションにまたがる結合やトランザクションは複雑化する。
2.2.2 垂直分割
垂直分割は、テーブルの列を複数のテーブルに分割する手法である。頻繁にアクセスされる列とそうでない列を分離することで、I/O負荷を低減し、キャッシュ効率を高める。正規化の一種と見なすこともできる。垂直分割では、結合操作の増加やデータ整合性の維持が課題となる。
2.3 並列処理
2.3.1 データ分割
データ分割は、大規模データセットを複数のプロセッサに分散させる手法である。各プロセッサは割り当てられたデータに対して独立して処理を行う。分割方式には、ブロック分割（連続データをブロック単位で分割）、サイクリック分割（ラウンドロビンで分散）、ブロックサイクリック分割（複数ブロックをサイクリックに割り当て）などがある。データ分割のバランスが悪いと、一部のプロセッサの負荷が高くなり、全体の性能が低下する。
2.3.2 タスク分割
タスク分割は、処理全体を複数の独立したタスクに分割し、それらを並列に実行する手法である。タスクの粒度が重要であり、細かすぎるとオーバーヘッドが増え、粗すぎると並列度が低下する。タスク分割は、パイプライン処理やフォーク・ジョインモデルでよく用いられる。タスク間の依存関係を適切に管理する必要がある。
3 分割に関連する技法
3.1 再帰的分割
再帰的分割は、問題をより小さな部分に分割し、各部分に対して同じ分割手順を再帰的に適用する技法である。分割統治法やフラクタル構造の生成に利用される。例えば、空間分割において、四分木（2次元空間の再帰的四分割）や八分木（3次元空間の再帰的八分割）が代表例である。再帰の深さが深くなるとスタックオーバーフローやメモリ消費が問題となる場合がある。
3.2 二分分割
二分分割は、集合や区間を二つの部分に分割する最も基本的な分割技法である。二分探索や二分木、二分決定図など、多くのアルゴリズムの基礎となる。二分分割は、分割の数が少なく処理が単純である一方、不均等分割により性能が劣化する可能性がある。バランスを保つために、赤黒木やAVL木などの自己平衡二分木が考案されている。
3.3 ハッシュによる分割
ハッシュによる分割は、データのキーにハッシュ関数を適用し、その結果に基づいて一定数のバケットにデータを割り当てる技法である。ハッシュ値の分布が均等であれば、データがほぼ均等に分割される。コンシステントハッシングは、ノードの追加・削除に伴う再分割を最小限に抑えるために開発された。ハッシュ分割は、分散データベースやキャッシュシステム（例：Redisクラスタ）で広く利用される。
4 分割の注意点と限界
4.1 過分割の問題
過分割とは、分割数が多すぎるために生じる問題である。データ構造や並列処理において、細かすぎる分割は管理オーバーヘッドや通信オーバーヘッドを増大させる。例えば、配列を過度に細かいブロックに分割すると、ブロックごとのインデックス計算やメモリ割り当てのコストが無視できなくなる。また、分割後の統合コストも分割数に比例して増加する傾向がある。過分割を避けるためには、分割の粒度を適切に設定し、アプリケーションの特性に応じた調整が必要である。
4.2 分割のバランス
分割のバランスは、各パーティションのサイズや負荷が均等であることを指す。バランスが悪いと、一部のパーティションに処理が集中し、全体の性能がボトルネックに支配される。クイックソートにおける不均等分割が最悪の場合O(n^2)になることはその一例である。データベースの水平分割では、データの偏りにより特定のパーティションだけが巨大化するホットスポット問題が発生する。バランスを保つためには、動的な再分割や適応的な分割戦略が採用されることがある。
4.3 分割後の結合コスト
分割された各部分を再び統合する際のコストは、分割の設計において重要な考慮点である。分割統治法では、統合フェーズが全体の効率を左右する。例えば、マージソートのマージ処理はO(n)であり、分割が均等であるため全体としてO(n log n)が達成される。しかし、分割が複雑になると、結合のために必要なデータの移動や再構成のコストが増大する。特に、分散システムにおける分割後のデータ結合には、ネットワーク転送や同期のオーバーヘッドが伴う。分割と結合のトレードオフを考慮した設計が不可欠である。